В теории вычислительной сложности SNP (от Strict NP ) — это класс сложности , содержащий ограниченное подмножество NP на основе его логической характеристики в терминах теоретико-графовых свойств. Он формирует основу для определения класса MaxSNP задач оптимизации .
Он определяется как класс задач, которые являются свойствами реляционных структур (таких как графы ), выражаемых формулой логики второго порядка следующего вида:
где — отношения структуры (например, отношение смежности для графа), — неизвестные отношения (множества кортежей вершин), а — формула без кванторов: любая булева комбинация отношений. [1] То есть, разрешена только экзистенциальная квантификация второго порядка (по отношениям) и разрешена только универсальная квантификация первого порядка (по вершинам). Если бы также была разрешена экзистенциальная квантификация по вершинам, то результирующий класс сложности был бы равен NP (точнее, классу тех свойств реляционных структур, которые находятся в NP), факт, известный как теорема Фейгина .
Например, SNP содержит 3-раскраску (задачу определения, является ли заданный граф 3-раскрашиваемым ), поскольку ее можно выразить следующей формулой:
Здесь обозначает отношение смежности входного графа, тогда как множества (унарные отношения) соответствуют множествам вершин, окрашенных в один из 3 цветов. Аналогично, SNP содержит задачу k -SAT: задачу выполнимости булевых операторов (SAT), где формула ограничена конъюнктивной нормальной формой и максимум k литералов на предложение, где k фиксировано.
Аналогичное определение рассматривает задачи оптимизации , когда вместо того, чтобы просить формулу быть удовлетворенной для всех кортежей, требуется максимизировать количество кортежей, для которых она удовлетворена. То есть, MaxSNP 0 определяется как класс задач оптимизации на реляционных структурах, выражаемых в следующей форме:
MaxSNP затем определяется как класс всех задач с L-редукцией ( линейной редукцией , а не логарифмической редукцией ) к задачам в MaxSNP 0 . [2] Например, MAX-3SAT является задачей в MaxSNP 0 : дан экземпляр 3-CNF-SAT ( задача выполнимости булевых функций с формулой в конъюнктивной нормальной форме и не более чем 3 литералами на предложение), найти назначение, удовлетворяющее как можно большему количеству предложений. Фактически, это естественная полная задача для MaxSNP .
Существует алгоритм аппроксимации с фиксированным отношением для решения любой задачи в MaxSNP , следовательно, MaxSNP содержится в APX , классе всех задач, аппроксимируемых с точностью до некоторого постоянного отношения. Фактически, замыкание MaxSNP при сокращениях PTAS (немного более общих, чем L-сокращения) равно APX ; то есть, каждая задача в APX имеет сокращение PTAS из некоторой задачи в MaxSNP . В частности, каждая MaxSNP -полная задача (при L-сокращениях или при AP-сокращениях ) также является APX -полной (при сокращениях PTAS) и, следовательно, не допускает PTAS, если P = NP . Однако доказательство этого опирается на теорему PCP , в то время как доказательства полноты MaxSNP часто являются элементарными.
{{cite book}}: CS1 maint: дата и год ( ссылка )