Кіріспе
PP алгоритмі > 1/2 < 1/2 < 1/2 > 1/2 Компьютерлік ғылымдағы мәселелер класы
Class of problems in computer science
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority P.
Күрделілік теориясында PP – бұл ықтималдық Тьюринг машинасымен полиномиалдық уақытта шешілетін шешімдік мәселелер класы, барлық жағдайларда қателік ықтималдығы 1/2-ден кем. PP аббревиатурасы ықтималдық полиномиалдық уақытты білдіреді. Бұл күрделік класын Гилл 1977 жылы анықтаған. Егер шешімдік мәселе PP класына жатса, онда оған монета лақтырып, кездейсоқ шешімдер қабылдауға рұқсат етілген алгоритм бар. Алгоритм полиномиалдық уақытта жұмыс істеуі кепілденеді. Жауап «Иә» болса, алгоритм 1/2-ден артық ықтималдықпен «Иә» деп жауап береді. Жауап «Жоқ» болса, алгоритм 1/2-ден кем ықтималдықпен «Иә» деп жауап береді. Практикалық тұрғыдан алғанда, бұл белгілі бір дәрежедегі дәлдікпен кездейсоқ, полиномиалдық уақыт алгоритмін жеткілікті (бірақ шектеулі) рет орындау арқылы шешуге болатын мәселелер класы. Полиномиалдық түрде шектелген және ықтималдыққа негізделген Тьюринг машиналары PPT деп танымал, яғни ықтималдық полиномиалдық уақыт машиналарын білдіреді. Тьюринг машиналарын сипаттау үшін шектелген қателік ықтималдығы міндетті емес. Сондықтан PP – бұл PPT машинасымен шешілетін барлық мәселелерді қамтитын күрделік класы, мұнда қателік ықтималдығы 1/2-ден кем. PP-нің тағы бір сипаттамасы – бұл полиномиалдық уақыттағы нөлдік детерминистік Тьюринг машинасымен шешілетін мәселелер жиынтығы, онда қабылдау шарты – есептеу жолдарының көпшілігінің (жартысынан артығы) қабылдауы. Осы себепті кейбір авторлар «Көпшілік P» деген балама атауды ұсынған.
Class of problems in computer science
In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977. If a decision problem is in PP, then there is an algorithm for it that is allowed to flip coins and make random decisions. It is guaranteed to run in polynomial time. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than 1/2. In more practical terms, it is the class of problems that can be solved to any fixed degree of accuracy by running a randomized, polynomial time algorithm a sufficient (but bounded) number of times. Turing machines that are polynomially bound and probabilistic are characterized as PPT, which stands for probabilistic polynomial time machines. This characterization of Turing machines does not require a bounded error probability. Hence, PP is the complexity class containing all problems solvable by a PPT machine with an error probability of less than 1/2. An alternative characterization of PP is the set of problems that can be solved by a nondeterministic Turing machine in polynomial time where the acceptance condition is that a majority (more than half) of computation paths accept. Because of this some authors have suggested the alternative name Majority P.
PP және BPP
BPP – PP-ның ішкі жиыны; оны тиімді ықтималдық алгоритмдері бар ішкі жиын ретінде қарастыруға болады. Айырмашылық – рұқсат етілген қателік ықтималдығында: BPP-да алгоритм дұрыс жауап беруі керек (ИӘ немесе ЖОҚ) ықтималдығы белгілі бір тұрақты c > 1/2-ден асып түсуі керек, мысалы 2/3 немесе 501/1000. Егер осылай болса, онда алгоритмді бірнеше рет іске қосып, көпшілік дауыс беру арқылы 1-ден кем дұрыс болу ықтималдығына Чернофф шектерін пайдаланып қол жеткізуге болады. Бұл қайталау саны c 1/2-ге жақындағанда артады, бірақ ол кіріс мөлшері n-ге байланысты емес. Көбірек айтқанда, егер c кіріс мөлшеріне полиномдық түрде тәуелді болса, яғни , онда алгоритмді қайталап, көпшілік дауыс аламыз. Хоффдинг теңсіздігі бойынша, бұл бізге BPP алгоритмін береді. Маңыздысы – осы c тұрақтысы кіріске тәуелді болмауы керек. Ал PP алгоритміне келесідей әрекет етуге рұқсат етіледі: ИӘ мысалында, кіріс ұзындығы n болғанда, 1/2 + 1/2n ықтималдығымен ИӘ деп шығару. ЖОҚ мысалында 1/2 - 1/2n ықтималдығымен ИӘ деп шығару. Осы екі ықтималдық экспоненциалды түрде жақын болғандықтан, тіпті оны полиномдық санда іске қоссақ та, ИӘ немесе ЖОҚ мысалымен жұмыс істеп жатқанымызды анықтау өте қиын. Көпшілік дауыс беру және Чернофф шектерін пайдаланып белгілі бір қажетті ықтималдық деңгейіне қол жеткізуге тырысу үшін n-ге экспоненциалды қайталау саны қажет болады.
More generally, if c can depend on the input size polynomially, as , then we can rerun the algorithm for and take the majority vote. By Hoeffding's inequality, this gives us a BPP algorithm. The important thing is that this constant c is not allowed to depend on the input. On the other hand, a PP algorithm is permitted to do something like the following:
On a YES instance, output YES with probability 1/2 + 1/2n, where n is the length of the input. On a NO instance, output YES with probability 1/2 − 1/2n. Because these two probabilities are exponentially close together, even if we run it for a polynomial number of times it is very difficult to tell whether we are operating on a YES instance or a NO instance. Attempting to achieve a fixed desired probability level using a majority vote and the Chernoff bound requires a number of repetitions that is exponential in n.
PP басқа күрделілік сыныптарымен салыстырғанда
PP-ге BPP кіреді, себебі BPP анықтамасында сипатталған ықтималдық алгоритмдер PP анықтамасындағылардың ішкі жиыны болып табылады. PP сондай-ақ NP-ді де қамтиды. Мұны дәлелдеу үшін NP-толық қанағаттандыру мәселесі PP класына жататынын көрсетеміз. F(x1, x2, ..., xn) формуласы берілгенде, x1, x2, ..., xn тапсырмасын тегіс түрде кездейсоқ таңдайтын ықтималдық алгоритмін қарастырайық. Содан кейін алгоритм тапсырманың F формуласын дұрыс ететінін тексереді. Егер дұрыс болса, ол «Иә» деп шығарады. Әйтпесе, ол «Иә» деп шығару үшін және «Жоқ» деп шығару үшін ықтималдығын пайдаланады. Егер формула қанағаттандырылмаса, алгоритм әрқашан «Иә» деп шығару үшін ықтималдығын пайдаланады. Егер қанағаттандыратын тапсырма болса, ол кем дегенде ықтималдығымен «Иә» деп шығарады (қанағаттандырмайтын тапсырма таңдалса, дәл 1/2, ал қанағаттандыратын тапсырма таңдалса, 1, орташа есеппен 1/2-ден жоғары). Осылайша, бұл алгоритм қанағаттандыру мәселесін PP класына жатқызады. SAT NP-толық болғандықтан және біз PP алгоритміне кез келген детерминистік полиномиалдық уақытты азайтуды қоса аламыз, NP PP класына кіреді. PP толықтыру бойынша жабық болғандықтан, ол сондай-ақ co-NP-ді қамтиды. Бұдан әрі, PP MA-ны қамтиды, ол алдыңғы екі кірісті қамтиды. PP сонымен қатар BQP-ны қамтиды, яғни тиімді полиномиалдық уақыт кванттық компьютерлерімен шешілетін шешімдер класын. Шын мәнінде, BQP PP үшін төмен, яғни PP машинасы BQP мәселелерін бірден шеше алудан ешқандай пайда таппайды. Кванттық компьютерлерде постселекциямен полиномиалдық уақыт класы PostBQP, PP-ге тең (төмендегі #PostBQP бөлімін қараңыз). Сонымен қатар, PP QMA-ны қамтиды, ол MA және BQP кірістілерін қамтиды. ПП оракулы бар полиномиалдық уақыт Тьюринг машинасы (PPP) PH-дегі барлық мәселелерді, яғни бүкіл полиномиалдық иерархияны шеше алады. Бұл нәтижені Сейносуке Тода 1989 жылы көрсетті және ол Тода теоремасы деп белгілі. Бұл PP класындағы мәселелерді шешудің қаншалықты қиын екенін көрсетеді. #P класы белгілі бір мағынада осыған тең, себебі P#P = PPP және демек P#P PH-ны да қамтиды. PP біркелкі TC0 класын қамтиды, яғни тұрақты тереңдіктегі, шексіз желдеткіші бар және көпшілік қақпалары бар бульдік схемалар, олар біркелкі (полиномиалдық уақыт алгоритмімен жасалған). PP PSPACE класына кіреді. Бұл MAJSAT үшін полиномиалдық кеңістіктегі алгоритмді көрсету арқылы оңай дәлелдеуге болады, ол төменде анықталған; жай ғана барлық тапсырмаларды тексеріп, қанағаттандыратындардың санын санаңыз. PP кез келген k үшін SIZE(nk) класына кірмейді (дәлелдеме).
If the formula is unsatisfiable, the algorithm will always output YES with probability If there exists a satisfying assignment, it will output YES with probability at least
(exactly 1/2 if it picked an unsatisfying assignment and 1 if it picked a satisfying assignment, averaging to some number greater than 1/2). Thus, this algorithm puts satisfiability in PP. As SAT is NP complete, and we can prefix any deterministic polynomial time many one reduction onto the PP algorithm, NP is included in PP. Because PP is closed under complement, it also includes co NP. Furthermore, PP includes MA, which subsumes the previous two inclusions. PP also includes BQP, the class of decision problems solvable by efficient polynomial time quantum computers. In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly. The class of polynomial time on quantum computers with postselection, PostBQP, is equal to PP (see #PostBQP below). Furthermore, PP includes QMA, which subsumes inclusions of MA and BQP. A polynomial time Turing machine with a PP oracle (PPP) can solve all problems in PH, the entire polynomial hierarchy. This result was shown by Seinosuke Toda in 1989 and is known as Toda's theorem. This is evidence of how hard it is to solve problems in PP. The class #P is in some sense about as hard, since P#P = PPP and therefore P#P includes PH as well. PP strictly includes uniform TC0, the class of constant depth, unbounded fan in boolean circuits with majority gates that are uniform (generated by a polynomial time algorithm). PP is included in PSPACE. This can be easily shown by exhibiting a polynomial space algorithm for MAJSAT, defined below; simply try all assignments and count the number of satisfying ones. PP is not included in SIZE(nk) for any k (proof).
Толық проблемалар және басқа қасиеттер
BPP-ден айырмашылығы, PP семантикалық емес, синтаксикалық класс. Кез келген полиномиалдық уақыттық ықтималдық машинасы PP класындағы кейбір тілді таниды. Керісінше, полиномиалдық уақыттық ықтималдық машинасының сипаттамасы берілген жағдайда, ол BPP класындағы тілді таниды ма, жоқ па, оны анықтау жалпы жағдайда шешілмейді. PP класында табиғи толық проблемалар бар, мысалы, MAJSAT. PP симметриялық айырыс бойынша жабық. PP класының одақ және қиылыс операцияларына қатысты жабылуы 14 жыл бойы ашық мәселе болып келді; бұл мәселенің оң шешімін Бейгел, Рейнгольд және Спилман тапты. Кейін Ли және Ааронсон басқа да дәлелдер келтірді (төмендегі #PostBQP бөлімін қараңыз).
PostBQP
Кванттық күрделілік класы BQP – кванттық Тьюринг машинасымен полиномдық уақытта шешілетін мәселелер класы. Постселекцияны қосу арқылы PostBQP деп аталатын кеңірек класс алынады. Шартты түрде, постселекция компьютерге мына мүмкіндікті береді: қандай да бір оқиғаның (мысалы, кубитті белгілі бір күйде өлшеу) нөлдік емес ықтималдығы болғанда, ол орын алады деп қарауға болады. Скотт Аронсон 2004 жылы PostBQP класы PP класына тең екенін дәлелдеді. PP-нің осы түрінде жаңадан қарастырылуы, PP қиылысу (және осыған байланысты бірігу) операциялары бойынша жабық екендігі, BQP PP үшін төмен екендігі және QMA PP класына кіретіндігі сияқты кейбір нәтижелерді көрсетуді жеңілдетеді.
PQP
PP сонымен қатар PQP деп аталатын тағы бір кванттық күрделілік класына тең, ол BQP-ның қателік шектеусіз аналогы болып табылады. Ол, барлық жағдайларда қателік ықтималдығы 1/2-ден кем болатындай, кванттық компьютердің көпмүшелік уақытында шешілетін шешімдер класын көрсетеді. PQP есептеу үшін қолданылатын барлық амплитудалар алгебралық сандардан құралса да, PQP PP-мен бірдей болып қалады.