Кіріспе
Компьютерлік ғылым тұжырымдамасы
Есептеу күрделілігі теориясында полиномиялық иерархия (кейде полиномиялық уақыт иерархиясы деп аталады) – NP және co NP кластарын кеңейтетін күрделілік сыныптарының иерархиясы. Иерархиядағы әрбір сынып PSPACE класына кіреді. Иерархияны оракул машиналары немесе ауыспалы Тьюринг машиналары арқылы анықтауға болады. Бұл математикалық логикадан алынған арифметикалық иерархия мен аналитикалық иерархияның ресурспен шектелген аналогы. Иерархиядағы сыныптардың бірігуі PH деп белгіленеді. Иерархиядағы сыныптар үшін полиномиалды уақыт азайтуларына қатысты толық проблемалар бар, олар кванторлардың ретіне шектеулер қойылған формулалар үшін сандық Буль формулалары орындала ма деп сұрайды. Иерархиядағы бір деңгейдегі немесе екі тікелей жанындағы деңгейлер арасындағы теңдік, иерархияның сол деңгейге "құлауына" әкелетіні белгілі.
Анықтамалар
Көптамалық иерархияның сыныптарына қатысты бірнеше балама анықтамалар бар.
Сандық Буль формуласының анықтамасы
Полиномиялық иерархияның экзистенциалдық/жалпылама анықтамасы үшін, L тілін (яғни, шешім проблемасы, {0,1}* жиынының ішкі жиыны) және p полиномын қарастырайық, сондай-ақ
where is some standard encoding of the pair of binary strings x and w as a single binary string. The language L represents a set of ordered pairs of strings, where the first string x is a member of , and the second string w is a "short" witness testifying that x is a member of In other words, if and only if there exists a short witness w such that Similarly, define
Note that De Morgan's laws hold: and , where Lc is the complement of L.
Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
Again, De Morgan's laws hold: and , where
The classes NP and co NP can be defined as , and , where P is the class of all feasibly (polynomial time) decidable languages. The polynomial hierarchy can be defined recursively as
Note that , and
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
мұндағы – x және w екілік тізбектерінің жұбының стандартты кодталуының бір екілік тізбек ретіндегі белгісі. L тілі – бұл реттелген тізбектер жұбының жиыны, мұндағы бірінші тізбек x – бұл жиынының мүшесі, ал екінші тізбек w – x мүшесі екенін куәландыратын "қысқа" куәлік. Басқаша айтқанда, егер және тек қана егер қысқа куәлік w болса, онда . Де Морган заңдары орындалады: және , мұндағы Lc – L тілінің толықтыруы. Бұл операторларды тілдердің толық кластарына қолдану үшін келесідей анықтаймыз:
where is some standard encoding of the pair of binary strings x and w as a single binary string. The language L represents a set of ordered pairs of strings, where the first string x is a member of , and the second string w is a "short" witness testifying that x is a member of In other words, if and only if there exists a short witness w such that Similarly, define
Note that De Morgan's laws hold: and , where Lc is the complement of L.
Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
Again, De Morgan's laws hold: and , where
The classes NP and co NP can be defined as , and , where P is the class of all feasibly (polynomial time) decidable languages. The polynomial hierarchy can be defined recursively as
Note that , and
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
Де Морган заңдары тағы да орындалады: және , мұндағы NP және co NP кластары , және , мұндағы P – барлық мүмкін (полиномиалдық уақытта) шешілетін тілдердің класы. Полиномиялық иерархия рекурсивті түрде келесідей анықталады:
where is some standard encoding of the pair of binary strings x and w as a single binary string. The language L represents a set of ordered pairs of strings, where the first string x is a member of , and the second string w is a "short" witness testifying that x is a member of In other words, if and only if there exists a short witness w such that Similarly, define
Note that De Morgan's laws hold: and , where Lc is the complement of L.
Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
Again, De Morgan's laws hold: and , where
The classes NP and co NP can be defined as , and , where P is the class of all feasibly (polynomial time) decidable languages. The polynomial hierarchy can be defined recursively as
Note that , and
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
, және Бұл анықтама полиномиялық иерархия мен арифметикалық иерархия арасындағы тығыз байланысты көрсетеді, мұндағы R және RE сәйкесінше P және NP рөлдерін атқарады. Аналитикалық иерархия да нақты сандардың ішкі жиындарының иерархиясын құру үшін ұқсас тәсілмен анықталады.
where is some standard encoding of the pair of binary strings x and w as a single binary string. The language L represents a set of ordered pairs of strings, where the first string x is a member of , and the second string w is a "short" witness testifying that x is a member of In other words, if and only if there exists a short witness w such that Similarly, define
Note that De Morgan's laws hold: and , where Lc is the complement of L.
Let be a class of languages. Extend these operators to work on whole classes of languages by the definition
Again, De Morgan's laws hold: and , where
The classes NP and co NP can be defined as , and , where P is the class of all feasibly (polynomial time) decidable languages. The polynomial hierarchy can be defined recursively as
Note that , and
This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers.
Түрлі Тьюринг машиналарының анықтамасы
Алма-қарсы Тьюринг машинасы – экзистенциалдық және әмбебап күйлерге бөлінген соңғы емес күйлері бар детерминистік емес Тьюринг машинасы. Ол қазіргі конфигурациясынан ақыр соңында қабылдайды, егер: ол экзистенциалдық күйде болса және ақыр соңында қабылдайтын конфигурацияға өте алса; немесе ол әмбебап күйде болса және барлық өтулер ақыр соңында қабылдайтын конфигурацияға өтетін болса; немесе ол қабылдау күйінде болса. Біз тілдер класын анықтаймыз, ол полиномиялық уақытта алма-қарсы Тьюринг машинасымен қабылданады, мұнда бастапқы күй экзистенциалдық күй болып табылады және машинаның өте алатын әрбір жолы экзистенциалдық және әмбебап күйлер арасында ең көп дегенде k-1 рет ауысады. Біз де осылай анықтаймыз, бірақ бастапқы күй әмбебап күй. Егер экзистенциалдық және әмбебап күйлер арасындағы ең көп дегенде k-1 ауысу талабын қалдырсақ, яғни тек алма-қарсы Тьюринг машинасының полиномиялық уақытта жұмыс істеуін талап етсек, онда бізде AP класының анықтамасы бар, ол PSPACE-ге тең.
Басқа кластармен қатынастар
Көптамалық иерархия – экспоненциалдық және арифметикалық иерархиялардың аналогы (әлдеқайда төмен күрделілікте). PH PSPACE ішіне кіретіні белгілі, бірақ екі класс тең бе екені әлі белгісіз. Бұл мәселенің бір пайдалы қайта формулировкасы: PH = PSPACE тек қана егер екінші реттік логика шекті құрылымдар бойынша қатынастардың транзитивті жабылу операторын (яғни, екінші реттік айнымалылар бойынша) қосу арқылы қосымша күш алмайтын болса ғана орындалады. Егер көптамалық иерархияда толық проблемалар болса, онда оның тек шекті санда ғана ерекше деңгейлері болады. PSPACE-толық проблемалар бар болғандықтан, егер PSPACE = PH болса, онда көптамалық иерархия құлдырауы керек, себебі PSPACE-толық проблема белгілі бір k үшін толық проблема болар еді. Көптамалық иерархиядағы әр класс толық проблемаларды қамтиды (көп уақыт бойынша толық проблемалар, көп бір азайту арқылы). Сонымен қатар, көптамалық иерархиядағы әр класс азайтулар бойынша жабық: яғни, иерархиядағы класс және тіл үшін, егер , онда да солай болады. Бұл екі факт бірге мынаны білдіреді: егер -тің толық проблемасы болса, онда , және мысалы, басқаша айтқанда, егер тіл белгілі бір оракулға негізделген болса, онда оны толық проблемаға негізделген деп қарастыруға болады. Сипсер–Лаутеман теоремасы BPP классы көптамалық иерархияның екінші деңгейінде орналасқанын көрсетеді. Каннан теоремасы кез келген k үшін SIZE(nk) ішіне кірмейтінін айтады. Тода теоремасы бойынша, көптамалық иерархия P#P ішіне кіреді.
Each class in the polynomial hierarchy contains complete problems (problems complete under polynomial time many one reductions). Furthermore, each class in the polynomial hierarchy is closed under reductions: meaning that for a class in the hierarchy and a language , if , then as well. These two facts together imply that if is a complete problem for , then , and For instance, In other words, if a language is defined based on some oracle in , then we can assume that it is defined based on a complete problem for Complete problems therefore act as "representatives" of the class for which they are complete. The Sipser–Lautemann theorem states that the class BPP is contained in the second level of the polynomial hierarchy. Kannan's theorem states that for any k, is not contained in SIZE(nk). Toda's theorem states that the polynomial hierarchy is contained in P#P.
Жалпы сілтемелер
А. Р. Мейер және Л. Ж. Стокмейер. Кезекті өрнектер үшін эквиваленттік мәселесінің квадраты экспоненциалдық кеңістік талап етеді. 13-ші IEEE Симпозиумының коммутациялау және автоматтар теориясы бойынша материалдары, 125–129 б., 1972 жыл. Полиномиялық иерархияны енгізген мақала. Л. Ж. Стокмейер. Полиномдық уақыт иерархиясы. Теориялық компьютерлік ғылым, 3-том, 1–22 б., 1976 жыл. С. Пападимитриу. Есептеу күрделігі. Аддисон Уэсли, 1994 жыл. 17-тарау. Полиномиялық иерархия, 409–438 бб. 7.2-бөлім: Полиномиялық иерархия, 161–167 бб.