Кіріспе
Егер NP біркелкі емес полиномиалдық уақыт класында болса, полиномиалдық иерархияның құлдырауы туралы Күрделілік теориясында Карп Липтон теоремасы Бульдік қанағаттандырылу проблемасын (SAT) логикалық қақпалардың полиномиалдық саны бар Бульдік схемалармен шеше алатындығын айтады, содан кейін және сондықтан Егер NP, нондетерминистік полиномиалдық уақыт проблемаларының класы, біркелкі емес полиномиалдық уақыт күрделілігі класы P / poly-да қамтылуы мүмкін деп есептесек, онда бұл болжам полиномиалдық иерархияның екінші деңгейінде құлдырауын білдіреді. Мұндай құлдырау мүмкін емес деп саналады, сондықтан теореманы күрделілік теоретиктері SAT немесе басқа NP толық проблемалары үшін көптамалық өлшем схемаларының жоқтығына дәлел ретінде қарастырады. Мұндай контурлардың жоқ екендігі дәлелденсе, P ≠ NP дегенді білдіреді. P/поли кездейсоқ полиномиалдық уақытпен шешілетін барлық мәселелерді қамтиды (Адлеман теоремасы), теорема сонымен қатар кездейсоқ пайдалану NP толық проблемалар үшін полиномиалдық уақыт алгоритмдеріне әкелмейтіндігіне дәлел болып табылады. Карп-Липтон теоремасы 1980 жылы алғаш рет дәлелдеген Ричард М. Карп пен Ричард Дж. Липтонның есімімен аталған. (Олардың бастапқы дәлелдері PH-ге дейін құлдырады , бірақ Майкл Сипсер оны жақсартты .) Теореманың варианттары, сол болжам бойынша, MA = AM, ал PH күрделілік класына құлайды. Егер PSPACE немесе басқа күрделілік сыныптары полиномиялық өлшемді контурларға ие деп есептелсе, мықты қорытынды жасауға болады; P/поли қараңыз. Егер 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)) кванттандырылмаған формуласына тең. Сондықтан, толық формула (ақиқат контур c бар деп болжам жасай отырып) формулаға тең, онда 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