СНП (сложность) - SNP (complexity) - Wikipedia

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

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

${\displaystyle \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})}$,

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

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

${\displaystyle \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 )}}$.

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

MaxSNP

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

${\displaystyle \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]Например, МАКС-3САТ проблема в 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-полнота часто бывает элементарной.

Смотрите также

• APX

Рекомендации

1. Федер, Томас; Варди, Моше Й. (1993). «Монотонный монадический SNP и удовлетворение ограничений». Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений. Дои:10.1145/167088.167245.
2. Papadimitriou, Christos H .; Яннакакис, Михалис (1991). «Оптимизация, аппроксимация и классы сложности». J. Comput. Syst. Наука. 43 (3): 425–440. Zbl  0765.68036.

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

внешняя ссылка

• Зоопарк сложности: SNP
• Зоопарк сложности: MaxSNP
• Зоопарк сложности: MaxSNP₀