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

В сложности вычислений теории 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]