Введение
В теории сложности теорема Карпа-Липтона гласит, что если булевую задачу удовлетворимости (SAT) можно решить булевыми цепями с полиномиальным числом логических ворот, то и следовательно, если мы предположим, что NP, класс недетерминированных многочленных задач во времени, может содержаться в неравномерном полиномиальном классе сложности времени P/poly, то это предположение подразумевает крах многочленной иерархии на втором уровне. Такой коллапс считается маловероятным, поэтому теорему обычно рассматривают теоретики сложности как доказательство несуществования цепей многочленного размера для SAT или для других NP-полных задач. Доказательство того, что таких цепей не существует, будет означать, что P ≠ NP. Поскольку P/poly содержит все проблемы, разрешимые в рандомизированном полиномиальном времени (теорема Адлемана), теорема также является доказательством того, что использование рандомизации не приводит к алгоритмам в полиномиальном времени для NP-полных проблем. Теорема Карпа-Липтона названа в честь Ричарда М. Карпа и Ричарда Дж. Липтона, которые впервые доказали ее в 1980 году. (Их первоначальное доказательство упало до PH , но Майкл Сипсер улучшил его до .) Варианты теоремы утверждают, что при том же предположении MA = AM, и PH переходит в класс сложности. Более убедительные выводы возможны, если предполагается, что PSPACE или некоторые другие классы сложности имеют схемы многочленного размера; см. P/poly. Если NP считается подмножеством BPP (которое является подмножеством P/poly), то иерархия полиномов сворачивается до BPP. Если coNP считается подмножеством NP/поли, то иерархия полиномов падает до третьего уровня.
In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then
and therefore
That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the polynomial hierarchy at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP complete problems. The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to , but Michael Sipser improved it to .) Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to complexity class. There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial sized circuits; see P/poly. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to BPP. If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level.
Интуиция
Предположим, что схемы многочленного размера для SAT не только существуют, но и могут быть построены алгоритмом многочленного времени. Тогда это предположение подразумевает, что сам SAT может быть решен алгоритмом многочленного времени, который строит схему, а затем применяет ее. То есть эффективно строимые схемы для SAT приведут к более сильному коллапсу, P = NP. Предположение теоремы Карпа-Липтона, что эти цепи существуют, является более слабым. Но все же возможно, чтобы алгоритм в классе сложности угадал правильную схему для SAT. Класс сложности описывает задачи формы, где любой полиномиальный срок является вычислимым предикатом. Экзистенциальная мощность первого количественного показателя в этом предикате может быть использована для угадывания правильной схемы для SAT, а универсальная мощность второго количественного показателя может быть использована для проверки правильности схемы. После того, как эта схема будет угадана и проверена, алгоритм в классе может использовать ее в качестве подпрограммы для решения других задач.
where is any polynomial time computable predicate. The existential power of the first quantifier in this predicate can be used to guess a correct circuit for SAT, and the universal power of the second quantifier can be used to verify that the circuit is correct. Once this circuit is guessed and verified, the algorithm in class can use it as a subroutine for solving other problems.
Доказательство теоремы Карпа Липтона
Теорема Карпа-Липтона может быть переформулирована в результате булевых формул с полиномиально ограниченными количественными знаками. Проблемы в описываются формулами такого типа, с синтаксисом где является многочленное время вычислимое предикат. Теорема Карпа-Липтона гласит, что этот тип формулы может быть преобразован в полиномиальное время в эквивалентную формулу, в которой количественники появляются в противоположном порядке; такая формула относится к Обратите внимание, что подформула является примером SAT. То есть, если c является действительной схемой для SAT, то эта подформула эквивалентна неквантифицированной формуле c ((s ((x)). Поэтому полная формула для эквивалентна (при предположении, что существует действительная схема с) формуле, где V - это формула, используемая для проверки того, что c действительно является действительной схемой с использованием саморедуктивности, как описано выше. Эта эквивалентная формула имеет свои количественные показатели в обратном порядке, как желательно. Поэтому предположение Карпа-Липтона позволяет нам перенести порядок экзистенциальных и универсальных квантификаторов в формулы такого типа, показывая, что повторение переноса позволяет формулам с более глубоким вложенным объединением упростить формулу, в которой они имеют один экзистенциальный квантификатор, за которым следует один универсальный квантификатор, показывая, что
where is a polynomial time computable predicate. The Karp–Lipton theorem states that this type of formula can be transformed in polynomial time into an equivalent formula in which the quantifiers appear in the opposite order; such a formula belongs to Note that the subformula
is an instance of SAT. That is, if c is a valid circuit for SAT, then this subformula is equivalent to the unquantified formula c(s(x)). Therefore, the full formula for is equivalent (under the assumption that a valid circuit c exists) to the formula
where V is the formula used to verify that c really is a valid circuit using self reducibility, as described above. This equivalent formula has its quantifiers in the opposite order, as desired. Therefore, the Karp–Lipton assumption allows us to transpose the order of existential and universal quantifiers in formulas of this type, showing that Repeating the transposition allows formulas with deeper nesting to be simplified to a form in which they have a single existential quantifier followed by a single universal quantifier, showing that