СНП (сложность)

В сложности вычислений теории SNP (от Strict NP ) — это класс сложности, содержащий ограниченное подмножество NP на основе его логической характеристики с точки зрения теоретико-графовых свойств. Он формирует основу для определения класса MaxSNP оптимизации задач .

Он определяется как класс проблем, которые являются свойствами реляционных структур (таких как графы ), выражаемых логической формулой второго порядка следующего вида:

\exists S_{1}\dots \exists S_{\ell }\,\forall v_{1}\dots \forall v_{m}\,\phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})

где $R_{1},\dots ,R_{k}$ являются отношениями структуры (например, отношением смежности для графа), $S_{1},\dots ,S_{\ell }$ неизвестные отношения (наборы кортежей вершин), а $\phi$ — это формула без кванторов: любая булева комбинация отношений. ^[1] То есть разрешена только экзистенциальная квантификация второго порядка (по отношениям) и только универсальная квантификация первого порядка (по вершинам). Если бы также была разрешена экзистенциальная квантификация по вершинам, результирующий класс сложности был бы равен NP (точнее, классу тех свойств реляционных структур, которые находятся в NP), факт, известный как теорема Феджина .

Например, SNP содержит 3-раскраску (задачу определения того, является ли данный граф 3-раскрашиваемым ), поскольку ее можно выразить следующей формулой:

\exists S_{1}\exists S_{2}\exists S_{3}\,\forall u\forall v\,{\bigl (}S_{1}(u)\vee S_{2}(u)\vee S_{3}(u){\bigr )}\,\wedge \,{\bigl (}E(u,v)\,\implies \,(\neg S_{1}(u)\vee \neg S_{1}(v))\,\wedge \,\left(\neg S_{2}(u)\vee \neg S_{2}(v)\right)\,\wedge \,(\neg S_{3}(u)\vee \neg S_{3}(v)){\bigr )}

Здесь $E$ обозначает отношение смежности входного графа, а множества (унарные отношения) $S_{1},S_{2},S_{3}$ соответствуют наборам вершин, окрашенных в один из трех цветов. Точно так же SNP содержит проблему k -SAT: булеву проблему выполнимости (SAT), где формула ограничена конъюнктивной нормальной формой и не более чем k литералами на предложение, где k фиксировано.

МаксСНП

Аналогичное определение рассматривает проблемы оптимизации , когда вместо того, чтобы требовать, чтобы формула выполнялась для всех кортежей, нужно максимизировать количество кортежей, для которых она удовлетворяется. То есть MaxSNP ₀ определяется как класс задач оптимизации реляционных структур, выражаемых в следующей форме:

\max \limits _{S_{1},\dots ,S_{\ell }}|\{(v_{1},\dots ,v_{m})\colon \phi (R_{1},\dots ,R_{k},S_{1},\dots ,S_{\ell },v_{1},\dots ,v_{m})\}|

MaxSNP затем определяется как класс всех проблем с L-редуцией ( линейной редукцией , а не лог-пространственной редукцией ) к проблемам в MaxSNP ₀ . ^[2] Например, MAX-3SAT является проблемой в MaxSNP ₀ : учитывая экземпляр 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 -полноты зачастую элементарны.

См. также

АПХ

Ссылки

^ Федер, Томас; Варди, Моше Ю. (1993). «Монотонный монадический SNP и удовлетворение ограничений». Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений - STOC '93 . стр. 612–622. дои : 10.1145/167088.167245 . ISBN 0897915917 . S2CID 9229294 . {{cite book}}: CS1 maint: дата и год ( ссылка )
^ Пападимитриу, Христос Х.; Яннакакис, Михалис (1991). «Классы оптимизации, аппроксимации и сложности». Дж. Компьютер. Сист. Наука . 43 (3): 425–440. дои : 10.1016/0022-0000(91)90023-X . Збл 0765.68036 .

Гредель, Эрих; Колайтис, Фокион Г.; Либкин Леонид ; Мартен, Маркс; Спенсер, Джоэл ; Варди, Моше Ю .; Венема, Иде; Вайнштейн, Скотт (2007). Теория конечных моделей и ее приложения . Тексты по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . п. 350 . ISBN 978-3-540-00428-8 . Збл 1133.03001 .

Внешние ссылки

[1] Федер, Томас; Варди, Моше Ю. (1993). «Монотонный монадический SNP и удовлетворение ограничений». Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений - STOC '93 . стр. 612–622. дои : 10.1145/167088.167245 . ISBN 0897915917 . S2CID 9229294 . {{cite book}}: CS1 maint: дата и год ( ссылка )

[2] Пападимитриу, Христос Х.; Яннакакис, Михалис (1991). «Классы оптимизации, аппроксимации и сложности». Дж. Компьютер. Сист. Наука . 43 (3): 425–440. дои : 10.1016/0022-0000(91)90023-X . Збл 0765.68036 .

[1]

[2]