В теории сложности , то Карп-Lipton теорема утверждает , что если проблема булевой выполнимости (SAT) может быть решена с помощью цепей булевых с полиномиальным числом логических элементов, то
- и поэтому
То есть, если мы предположим, что NP , класс недетерминированных полиномиальных задач времени, может содержаться в неоднородном классе полиномиальной временной сложности P / poly , то это предположение подразумевает коллапс полиномиальной иерархии на ее втором уровне. Такой коллапс считается маловероятным, поэтому теоретики сложности обычно рассматривают эту теорему как свидетельство отсутствия схем полиномиального размера для SAT или других NP-полных задач. Доказательство того, что таких схем не существует, означало бы, что P ≠ NP . Поскольку P / poly содержит все задачи, разрешимые за рандомизированное полиномиальное время ( теорема Адлемана), теорема Карпа – Липтона также свидетельствует о том, что использование рандомизации не приводит к алгоритмам за полиномиальное время для NP-полных задач.
Теорема Карпа-Липтона названа в честь Ричарда М. Карпа и Ричарда Дж. Липтона , которые впервые доказали ее в 1980 году (их первоначальное доказательство свернуло PH до, но Майкл Сипсер улучшил его до.)
Варианты теоремы утверждают, что при том же предположении MA = AM , а PH коллапсирует в SП
2класс сложности. Возможны более сильные выводы, если предполагается, что PSPACE или некоторые другие классы сложности имеют схемы полиномиального размера; см. P / poly . Если предполагается, что NP является подмножеством BPP (которое является подмножеством P / poly), тогда иерархия полиномов сворачивается до BPP . [1] Если предполагается, что coNP является подмножеством NP / poly , тогда иерархия полиномов сворачивается до третьего уровня.
Интуиция
Предположим, что схемы для SAT не только существуют, но и могут быть построены с помощью алгоритма полиномиального времени. Тогда это предположение подразумевает, что сама SAT может быть решена с помощью алгоритма полиномиального времени, который строит схему, а затем применяет ее. То есть эффективно построенные схемы для SAT приведут к более сильному коллапсу, P = NP.
Предположение теоремы Карпа – Липтона о существовании таких схем более слабое. Но это все еще возможно для алгоритма класса сложностичтобы угадать правильную схему для SAT. Класс сложности описывает проблемы формы
где - любой предикат, вычислимый за полиномиальное время. Экзистенциальная мощность первого квантификатора в этом предикате может использоваться, чтобы угадать правильную схему для SAT, а универсальная мощность второго квантора может использоваться для проверки правильности схемы. Как только эта схема будет угадана и проверена, алгоритм в классе может использовать его как подпрограмму для решения других проблем.
Самовосстановление
Чтобы понять доказательство Карпа – Липтона более подробно, мы рассмотрим проблему проверки того, является ли схема c правильной схемой для решения экземпляров SAT заданного размера, и покажем, что эта проблема проверки схемы относится к. То есть, существует полиномиальное время вычислимого предикат V таким образом, что с является правильной цепью , если и только если для все полиномиально-ограниченного г , V ( с , г ) истинно.
Схема c является правильной схемой для SAT, если она удовлетворяет двум свойствам:
- Для каждой пары ( s , x ), где s - экземпляр SAT, а x - решение этого экземпляра, c ( s ) должно быть истинным.
- Для каждого экземпляра s SAT, для которого c ( s ) истинно, s должен быть разрешимым.
Первое из этих двух свойств уже в форме задач в классе . Чтобы проверить второе свойство, мы используем свойство самосводимости SAT.
Самосводимость описывает феномен, когда мы можем быстро проверить, разрешима ли экземпляр SAT, мы можем почти так же быстро найти явное решение для этого экземпляра. Чтобы найти решение экземпляра s , выберите одну из логических переменных x, которая вводится в s , и сделайте два меньших экземпляра s 0 и s 1, где s i обозначает формулу, образованную заменой x на константу i . Как только эти два меньших экземпляра будут построены, примените тест на разрешимость к каждому из них. Если один из этих двух тестов возвращает, что меньший экземпляр является удовлетворительным, продолжайте решение этого экземпляра, пока не будет получено полное решение.
Чтобы использовать самовосстановление для проверки второго свойства правильной схемы для SAT, мы перепишем его следующим образом:
- Для каждого экземпляра s SAT, для которого c ( s ) истинно, описанная выше процедура самосокращения находит допустимое решение s .
Таким образом, мы можем протестировать в является ли c допустимой схемой для решения SAT.
см. случайную самовосстановимость для получения дополнительной информации.
Доказательство теоремы Карпа – Липтона.
Теорема Карпа – Липтона может быть переформулирована как результат о булевых формулах с полиномиально ограниченными кванторами. Проблемы в описываются формулами этого типа с синтаксисом
где является вычислимым предикатом за полиномиальное время. Теорема Карпа – Липтона утверждает, что этот тип формул может быть преобразован за полиномиальное время в эквивалентную формулу, в которой кванторы появляются в обратном порядке; такая формула принадлежит. Обратите внимание, что подформула
является экземпляром SAT. То есть, если c является допустимой схемой для SAT, то эта подформула эквивалентна неквантифицированной формуле c ( s ( x )). Следовательно, полная формула дляэквивалентно (в предположении, что действительная схема c существует) формуле
где V - формула, используемая для проверки того, что c действительно является допустимой схемой с использованием самовосстановления, как описано выше. Эта эквивалентная формула имеет свои кванторы в обратном порядке, как и требуется. Следовательно, предположение Карпа – Липтона позволяет нам переставить порядок экзистенциальных и универсальных кванторов в формулах этого типа, показывая, что Повторение транспонирования позволяет упростить формулы с более глубоким вложением до формы, в которой они имеют один квантор существования, за которым следует один универсальный квантор, показывая, что
Еще одно доказательство и S 2 P
Предполагать . Следовательно, существует семейство схемчто решает выполнимость при вводе длины n . Используя самосводимость, существует семейство схем который выводит удовлетворительное присвоение истинным экземплярам.
Предположим, что L - набор
С можно рассматривать как пример SAT (по теореме Кука-Левина ), существует схема, в зависимости от , такая, что формула, определяющая L , эквивалентна
( 1 )
Кроме того, схему можно угадать с помощью экзистенциальной количественной оценки:
( 2 )
Очевидно, из ( 1 ) следует ( 2 ). Если (1) ложно, то. В этом случае ни одна из цепей D не может вывести задание назначения. правда.
Доказательство показало, что набор в .
Более того, если формула верна, то схема D будет работать против любого x . Еслиформула ложна, то x, делающий формулу (1) ложной, будет работать против любой схемы. Это свойство означает более сильный коллапс, а именно к SП
2 класс сложности (т.е. ). Это наблюдал Сенгупта. [2]
AM = MA
Модификация [3] приведенного выше доказательства дает
(см. протокол Артура-Мерлина ).
Предположим, что L находится в AM , то есть:
и как ранее перепишем используя схему который выводит удовлетворительное задание, если оно существует:
С можно догадаться:
что доказывает находится в меньшем классе MA .
Приложение к нижним оценкам схемы - теорема Каннана
Kannan теорема «сек [4] утверждает , что для любого фиксированного к существует язык в , которого нет в SIZE (n k ) (Это другое утверждение, чем, который в настоящее время открыт и утверждает, что существует единственный язык, которого нет в SIZE (n k ) для любого k ). Это простая нижняя граница схемы .
Схема доказательства:
Существует язык (в доказательстве используется техника диагонализации ). Рассмотрим два случая:
- Если тогда и теорема доказана.
- Если , то по теореме Карпа – Липтона и поэтому .
Более сильная версия теоремы Карпа – Липтона усиливает теорему Каннана следующим образом: для любого k существует язык.
Также известно, что PP не содержится в, что было доказано Винодчандраном. [5] Доказательство: [6]
- Если тогда .
- Иначе, . С
- (в собственности МА )
- (по теореме Тоды и свойству MA)
- (следует из предположения об использовании интерактивного протокола для постоянного, см. P / poly )
- сдерживания равны, и мы получаем по теореме Каннана.
Рекомендации
- ^ С. Захос , Вероятностные кванторы и игры, 1988
- ↑ Jin Yi-Cai. [1] , раздел 6
- ^ В. Арвинд, Дж. Кёблер, У. Шёнинг , Р. Шулер, Если NP имеет схемы полиномиального размера, то MA = AM
- ^ Kannan, R. (1982). «Нижние границы размера схемы и несводимость к разреженным множествам». Информация и контроль . 55 (1–3): 40–56. DOI : 10.1016 / S0019-9958 (82) 90382-5 .
- ^ Н. В. Винодчандран, Замечание о схемной сложности PP
- ^ С. Ааронсон , Оракулы хитрые, но не вредоносные
- Карп, РМ ; Lipton, RJ (1980), "Некоторые связи между неоднородными и однородными классами сложности", Труды двенадцатого ежегодного симпозиума ACM по теории вычислений , стр. 302–309, doi : 10.1145 / 800141.804678.
- Карп, РМ ; Lipton, RJ (1982), Машины Тьюринга , которые принимают советы , 28 , стр 191-209,. DOI : 10.5169 / тюлени-52237.