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

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

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

,

куда отношения структуры (например, отношение смежности для графа), - неизвестные отношения (множества наборов вершин), и - бескванторная формула: любая логическая комбинация отношений.[1] То есть разрешена только экзистенциальная квантификация второго порядка (по отношениям) и разрешена только универсальная квантификация первого порядка (по вершинам). Если бы экзистенциальная квантификация по вершинам также была разрешена, результирующий класс сложности был бы равен NP (точнее, , класс тех свойств реляционных структур, которые находятся в NP), факт, известный как Теорема Феджина.

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

.

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

MaxSNP

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

MaxSNP тогда определяется как класс всех задач с L-редукция (линейная редукция, нет сокращение пространства журнала) к проблемам в MaxSNP0.[2]Например, МАКС-3САТ проблема в MaxSNP0: с учетом экземпляра 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-полнота часто бывает элементарной.

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

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

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

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