SNP (сложность)
В теории вычислительной сложности SNP ( от Strict NP ) — класс сложности, содержащий ограниченное подмножество NP на основе его логической характеристики с точки зрения теоретико-графовых свойств. Он формирует основу для определения класса MaxSNP задач оптимизации .
Он определяется как класс проблем, которые являются свойствами реляционных структур (таких как графы ), выражаемыми логической формулой второго порядка следующего вида:
где - отношения структуры (например, отношение смежности для графа), - неизвестные отношения (наборы кортежей вершин), и - бескванторная формула: любая логическая комбинация отношений. [1] То есть разрешена только экзистенциальная квантификация второго порядка (по отношениям) и только универсальная квантификация первого порядка (по вершинам). Если бы также была разрешена экзистенциальная квантификация над вершинами, результирующий класс сложности был бы равен NP (точнее, классу тех свойств реляционных структур, которые находятся в NP), факт, известный как теорема Феджина .
Например, SNP содержит 3-раскраску (задачу определения, является ли данный граф 3-раскрашиваемым ), потому что его можно выразить следующей формулой:
Здесь обозначает отношение смежности входного графа, а множества (унарные отношения) соответствуют множествам вершин, окрашенных в один из 3-х цветов. Точно так же SNP содержит проблему k -SAT: логическую проблему выполнимости (SAT), где формула ограничена конъюнктивной нормальной формой и не более чем k литералов на предложение, где k фиксировано.
Аналогичное определение рассматривает задачи оптимизации , когда вместо того, чтобы требовать, чтобы формула выполнялась для всех кортежей, нужно максимизировать количество кортежей, для которых она выполняется. То есть MaxSNP 0 определяется как класс задач оптимизации на реляционных структурах, выражаемый в следующем виде: