В теории сложности вычислений , СНП (от строгого NP ) представляет собой класс сложность , содержащая ограниченное подмножество NP на основе его логической характеристики в терминах графов теоретико- свойств. Она является основой для определения класса MaxSNP из задач оптимизации .
Он определяется как класс проблем, которые являются свойствами реляционных структур (таких как графы ), выражаемых логической формулой второго порядка следующего вида:
- ,
где отношения структуры (например, отношение смежности для графа), неизвестные отношения (наборы кортежей вершин) и бескванторная формула: любая логическая комбинация отношений. [1] То есть разрешена только экзистенциальная количественная оценка второго порядка (по отношениям) и разрешена только универсальная количественная оценка первого порядка (по вершинам). Если бы экзистенциальная квантификация по вершинам также была разрешена, результирующий класс сложности был бы равен NP (точнее, классу тех свойств реляционных структур, которые находятся в NP), факт, известный как теорема Феджина .
Например, SNP содержит 3-раскраску (проблема определения того, является ли данный граф 3-раскрашиваемым ), потому что ее можно выразить следующей формулой:
- .
Здесь обозначает отношение смежности входного графа, а наборы (унарные отношения) соответствуют наборам вершин, окрашенным в один из трех цветов. Аналогично, SNP содержит проблему k -SAT: проблему логической выполнимости (SAT), в которой формула ограничивается конъюнктивной нормальной формой и не более чем k литералами на предложение, где k фиксировано.
MaxSNP [ править ]
Аналогичное определение рассматривает проблемы оптимизации , когда вместо того, чтобы требовать выполнения формулы для всех кортежей, нужно максимизировать количество кортежей, для которых она удовлетворяется. То есть 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 -полноты часто являются элементарными.
См. Также [ править ]
Ссылки [ править ]
- ^ Федер, Томас; Варди, Моше Ю. (1993). «Монотонный монадический SNP и удовлетворение ограничений». Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений . DOI : 10.1145 / 167088.167245 .
- ^ Пападимитриу, Христос Х .; Яннакакис, Михалис (1991). «Оптимизация, аппроксимация и классы сложности». J. Comput. Syst. Sci . 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 0
