25:
3362:
2626:
4367:
4238:
4227:
2524:
is a non-deterministic Turing machine with non-final states partitioned into existential and universal states. It is eventually accepting from its current configuration if: it is in an existential state and can transition into some eventually accepting configuration; or, it is in a universal state
984:
1434:
4362:{\displaystyle {\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\text{there exists a circuit }}B{\text{ with at most }}k{\text{ gates }}\\{\text{ such that }}A{\text{ and }}B{\text{ compute the same function}}\end{matrix}}\right.\right\}}
1796:
1701:
4067:
4456:
1955:
1877:
2729:
2816:
269:
726:
2368:
2295:
433:
514:
358:
2030:
2222:
2881:
816:
1269:
1589:
1515:
164:
hold, for formulae with restrictions on the quantifier order. It is known that equality between classes on the same level or consecutive levels in the hierarchy would imply a "collapse" of the hierarchy to that level.
3917:
2945:
2886:
Unlike the arithmetic and analytic hierarchies, whose inclusions are known to be proper, it is an open question whether any of these inclusions are proper, though it is widely believed that they all are. If any
2149:
3083:
3782:
2094:
3855:
3349:
2999:
1707:
1612:
4786:
3258:
780:
4222:{\displaystyle L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}}
2418:
2471:
4537:
1044:
2562:
to be the class of languages accepted by an alternating Turing machine in polynomial time such that the initial state is an existential state and every path the machine can take swaps at most
5015:
3624:
4374:
3546:
3508:
4603:
1882:
1804:
2648:
640:
4847:
4700:
4640:
4027:
3715:
3465:
2560:
1261:
598:
2607:– 1 swaps between the existential and universal states, so that we only require that our alternating Turing machine runs in polynomial time, then we have the definition of the class
550:
4881:
3163:
2598:
2735:
4492:
3654:
3582:
187:
1219:
1149:
1183:
1090:
3973:
645:
3270:
The question of collapse to the first level is generally thought to be extremely difficult. Most researchers do not believe in a collapse, even to the second level.
3029:
3681:
2301:
2228:
364:
439:
292:
1960:
979:{\displaystyle \exists ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\exists w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\},}
2163:
1429:{\displaystyle \forall ^{p}L:=\left\{x\in \{0,1\}^{*}\ \left|\ \left(\forall w\in \{0,1\}^{\leq p(|x|)}\right)\langle x,w\rangle \in L\right.\right\}}
2822:
1520:
1446:
54:
3860:
3355:
3264:
5192:
2890:
2099:
4898:
A Garey/Johnson-style list of problems known to be complete for the second and higher levels of the polynomial hierarchy can be found in
3510:-complete problems (problems complete under polynomial-time many-one reductions). Furthermore, each class in the polynomial hierarchy is
3034:
1791:{\displaystyle \forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}
1696:{\displaystyle \exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}}
3720:
2050:
4974:
3787:
3295:
2950:
4729:
3414:, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if and only if
782:
is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for some NP-complete problem.
3219:
731:
3935:
3433:
problems, we know that if PSPACE = PH, then the polynomial hierarchy must collapse, since a PSPACE-complete problem would be a
2376:
5589:
4952:
2423:
4497:
2157:
is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as
992:
4451:{\displaystyle {\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})}
5554:
5112:
5024:
3587:
1950:{\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}
1872:{\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}
76:
47:
5185:
3515:
3477:
2724:{\displaystyle \Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}}
4558:
2488:
90:
603:
4818:
4671:
4665:
4611:
3998:
3686:
3436:
3279:
2531:
1228:
567:
2811:{\displaystyle \Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}}
522:
4852:
3134:
2569:
264:{\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},}
3931:
5599:
5178:
4465:
3629:
3557:
4849:. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for
1606:
be a class of languages. Extend these operators to work on whole classes of languages by the definition
1188:
5570:
5377:
2525:
and every transition is into some eventually accepting configuration; or, it is in an accepting state.
2521:
161:
132:
157:
37:
1099:
5559:
4985:
4959:
section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
2509:
1158:
1065:
41:
33:
3951:
3941:
3927:. Complete problems therefore act as "representatives" of the class for which they are complete.
102:
721:{\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}}
5513:
4995:
3404:
2477:
136:
58:
4971:. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.
5508:
5503:
4918:
3400:
2629:
Commutative diagram equivalent to the polynomial time hierarchy. The arrows denote inclusion.
3008:
5107:. Discrete Mathematics and Its Applications (2nd ed.). CRC Press. pp. 1308–1314.
4923:
4031:
3659:
140:
8:
3089:
2363:{\displaystyle \Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}}
2290:{\displaystyle \Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}}
1440:
5594:
5147:
3419:
2505:
2482:
2476:
This definition reflects the close connection between the polynomial hierarchy and the
428:{\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}}
144:
509:{\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}}
353:{\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}
173:
There are multiple equivalent definitions of the classes of the polynomial hierarchy.
5518:
5108:
5020:
4948:
3982:
2025:{\displaystyle {\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}
4978:, pp. 125–129, 1972. The paper that introduced the polynomial hierarchy.
5482:
5372:
5304:
5294:
5201:
5151:
5137:
5010:
5006:
4981:
4968:
4883:. Each language is a subset of the problem obtained by removing the restriction of
4044:
3426:
3381:
799:
553:
279:
106:
5103:
Hemaspaandra, Lane (2018). "17.5 Complexity classes". In Rosen, Kenneth H. (ed.).
5477:
5467:
5424:
5414:
5407:
5397:
5387:
5345:
5340:
5335:
5319:
5299:
5277:
5272:
5267:
5255:
5250:
5245:
5240:
5057:
Completeness in the
Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans
4964:
4942:
3430:
3415:
3389:
3373:
3085:. In particular, we have the following implications involving unsolved problems:
2635:
2500:
2037:
795:
283:
149:
111:
4899:
3361:
2217:{\displaystyle \Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}}
5472:
5360:
5282:
5235:
5142:
5129:
3369:
2494:
2153:
561:
557:
275:
128:
3422:
operator over relations of relations (i.e., over the second-order variables).
2876:{\displaystyle \Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}}
5583:
3365:
2633:
The union of all classes in the polynomial hierarchy is the complexity class
3283:
3207:
2625:
1584:{\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}
1510:{\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}
3399:
The polynomial hierarchy is an analogue (at much lower complexity) of the
790:
For the existential/universal definition of the polynomial hierarchy, let
5350:
5260:
3923:, then we can assume that it is defined based on a complete problem for
3912:{\displaystyle \Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}}
2620:
5462:
5287:
2508:
is also defined in a similar way to give a hierarchy of subsets of the
807:
5016:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
5457:
5170:
5005:
2940:{\displaystyle \Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}}
1058:
represents a set of ordered pairs of strings, where the first string
156:
Classes within the hierarchy have complete problems (with respect to
2144:{\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}}
5452:
5447:
5392:
5215:
3919:. In other words, if a language is defined based on some oracle in
3429:, then it has only finitely many distinct levels. Since there are
3078:{\displaystyle \Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P}}}
3777:{\displaystyle \Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}}
2089:{\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}}
5442:
5128:
Ferrarotti, Flavio; Van den
Bussche, Jan; Virtema, Jonni (2018).
4913:
3850:{\displaystyle \Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}}
3344:{\displaystyle {\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}}
5127:
2994:{\displaystyle \Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}}
5549:
5544:
5419:
5402:
4781:{\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\ldots f}
3411:
3393:
3385:
2613:
2600:
similarly, except that the initial state is a universal state.
123:
4998:. Computational Complexity. Addison-Wesley, 1994. Chapter 17.
3938:
is contained in the second level of the polynomial hierarchy.
2566:– 1 times between existential and universal states. We define
181:
For the oracle definition of the polynomial hierarchy, define
5539:
5534:
5355:
3377:
3115:
2043:
117:
3253:{\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {NP}}}
775:{\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}}
5367:
5225:
5130:"Expressivity Within Second-Order Transitive-Closure Logic"
4892:
4351:
4211:
1418:
965:
4790:
That is, is there an assignment of values to variables in
5382:
5314:
5309:
5230:
5220:
4524:
4383:
4247:
2515:
785:
5031:
Section 7.2: The
Polynomial Hierarchy, pp. 161–167.
3985:
states that the polynomial hierarchy is contained in P.
2413:{\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}}
1046:
is some standard encoding of the pair of binary strings
4804:, there exists an assignment of values to variables in
2466:{\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}}
147:. The union of the classes in the hierarchy is denoted
4298:
5136:. Schloss-Dagstuhl - Leibniz Zentrum fĂĽr Informatik.
4855:
4821:
4732:
4674:
4614:
4561:
4532:{\displaystyle \langle A,k\rangle \in {\mathit {CM}}}
4500:
4468:
4377:
4241:
4070:
4001:
3954:
3863:
3790:
3723:
3689:
3662:
3632:
3590:
3560:
3518:
3480:
3439:
3298:
3222:
3137:
3037:
3011:
2953:
2893:
2825:
2738:
2651:
2621:
Relations between classes in the polynomial hierarchy
2572:
2534:
2426:
2379:
2304:
2231:
2166:
2102:
2053:
1963:
1885:
1807:
1710:
1615:
1523:
1449:
1272:
1231:
1191:
1161:
1102:
1068:
995:
819:
734:
648:
606:
570:
525:
442:
367:
295:
190:
4644:
satisfiability for quantified
Boolean formulas with
3285:
3280:
PH (complexity) § Relationship to other classes
3209:
4462:is decidable in polynomial time and because, given
5105:Handbook of Discrete and Combinatorial Mathematics
4875:
4841:
4780:
4702:. In this problem, we are given a Boolean formula
4694:
4634:
4597:
4531:
4486:
4450:
4361:
4221:
4021:
3967:
3911:
3849:
3776:
3709:
3675:
3648:
3618:
3576:
3540:
3502:
3459:
3343:
3252:
3157:
3077:
3023:
2993:
2939:
2875:
2810:
2723:
2592:
2554:
2465:
2412:
2362:
2289:
2216:
2143:
2088:
2024:
1949:
1871:
1790:
1695:
1583:
1509:
1428:
1255:
1213:
1177:
1143:
1084:
1039:{\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}
1038:
978:
774:
720:
634:
592:
564:for some complete problem in class A; the classes
544:
508:
427:
352:
263:
121:. Each class in the hierarchy is contained within
4062:be the set of all boolean circuits. The language
3418:gains no additional power from the addition of a
3273:
5581:
5134:DROPS-IDN/V2/Document/10.4230/LIPIcs.CSL.2018.22
3656:as well. These two facts together imply that if
3474:Each class in the polynomial hierarchy contains
46:but its sources remain unclear because it lacks
4050:, determine if there is a circuit with at most
3619:{\displaystyle A\leq _{\rm {m}}^{\mathsf {P}}L}
4232:is decidable in polynomial time. The language
135:. It is a resource-bounded counterpart to the
5186:
3541:{\displaystyle \leq _{\rm {m}}^{\mathsf {P}}}
3503:{\displaystyle \leq _{\rm {m}}^{\mathsf {P}}}
1221:if and only if there exists a short witness
5102:
4797:such that, for all assignments of values in
4598:{\displaystyle \langle A,k,B,x\rangle \in L}
4586:
4562:
4513:
4501:
4481:
4469:
4272:
4260:
4153:
4140:
4106:
4082:
3356:(more unsolved problems in computer science)
3265:(more unsolved problems in computer science)
1408:
1396:
1360:
1347:
1313:
1300:
1244:
1232:
1027:
1014:
1008:
996:
955:
943:
907:
894:
860:
847:
4815:is true? The variant above is complete for
4724:. We have to determine if it is true that
5193:
5179:
4975:Symposium on Switching and Automata Theory
4940:
635:{\displaystyle {\mathsf {coNP}}^{\rm {A}}}
5141:
4842:{\displaystyle \Sigma _{k}^{\mathsf {P}}}
4695:{\displaystyle \Sigma _{k}^{\mathsf {P}}}
4635:{\displaystyle \Sigma _{k}^{\mathsf {P}}}
4289:
4123:
4022:{\displaystyle \Sigma _{2}^{\mathsf {P}}}
3710:{\displaystyle \Sigma _{i}^{\mathsf {P}}}
3460:{\displaystyle \Sigma _{k}^{\mathsf {P}}}
3416:second-order logic over finite structures
2555:{\displaystyle \Sigma _{k}^{\mathsf {P}}}
77:Learn how and when to remove this message
3410:It is known that PH is contained within
3360:
2624:
1256:{\displaystyle \langle x,w\rangle \in L}
1054:as a single binary string. The language
593:{\displaystyle {\mathsf {NP}}^{\rm {A}}}
642:are defined analogously. For example,
545:{\displaystyle {\mathsf {P}}^{\rm {A}}}
5582:
5200:
4876:{\displaystyle \Pi _{k}^{\mathsf {P}}}
4867:
4833:
4686:
4626:
4440:
4432:
4420:
4402:
4371:is the circuit minimization language.
4054:gates that computes the same function
4013:
3903:
3900:
3897:
3890:
3887:
3875:
3829:
3826:
3823:
3820:
3808:
3756:
3753:
3741:
3701:
3607:
3532:
3494:
3451:
3336:
3333:
3330:
3327:
3324:
3321:
3304:
3301:
3245:
3242:
3225:
3158:{\displaystyle \Pi _{1}^{\mathsf {P}}}
3149:
3069:
3049:
2985:
2965:
2931:
2905:
2867:
2851:
2848:
2837:
2802:
2776:
2750:
2715:
2689:
2663:
2603:If we omit the requirement of at most
2593:{\displaystyle \Pi _{k}^{\mathsf {P}}}
2584:
2546:
2516:Alternating Turing machines definition
2457:
2438:
2435:
2432:
2429:
2404:
2385:
2382:
2354:
2337:
2322:
2281:
2264:
2249:
2209:
2198:
2178:
2136:
2128:
2114:
2111:
2108:
2105:
2081:
2073:
2059:
2056:
1969:
1966:
1935:
1932:
1924:
1902:
1891:
1888:
1857:
1854:
1846:
1824:
1813:
1810:
1717:
1622:
786:Quantified boolean formulae definition
765:
762:
758:
746:
713:
710:
707:
704:
693:
674:
671:
660:
619:
616:
613:
610:
577:
574:
529:
498:
481:
478:
475:
472:
460:
417:
400:
397:
385:
342:
325:
313:
253:
242:
222:
202:
5174:
4934:
2642:The definitions imply the relations:
127:. The hierarchy can be defined using
4944:Complexity Theory: A Modern Approach
4941:Arora, Sanjeev; Barak, Boaz (2009).
3425:If the polynomial hierarchy has any
3286:Unsolved problem in computer science
3210:Unsolved problem in computer science
176:
18:
4992:, vol.3, pp. 1–22, 1976.
4487:{\displaystyle \langle A,k\rangle }
3995:An example of a natural problem in
3649:{\displaystyle A\in {\mathcal {C}}}
3577:{\displaystyle L\in {\mathcal {C}}}
13:
5093:Arora and Barak, 2009, Theorem 5.4
4857:
4823:
4759:
4746:
4733:
4676:
4616:
4521:
4427:
4415:
4392:
4380:
4280:
4244:
4132:
4114:
4003:
3956:
3865:
3792:
3725:
3691:
3641:
3600:
3569:
3525:
3487:
3441:
3139:
3059:
3039:
2975:
2955:
2915:
2895:
2857:
2827:
2786:
2760:
2740:
2699:
2673:
2653:
2574:
2536:
2447:
2394:
2344:
2332:
2306:
2271:
2259:
2233:
2188:
2168:
2123:
2068:
2012:
1976:
1942:
1919:
1910:
1897:
1864:
1841:
1832:
1819:
1778:
1739:
1725:
1712:
1683:
1644:
1630:
1617:
1575:
1560:
1550:
1531:
1501:
1486:
1476:
1457:
1338:
1274:
1214:{\displaystyle x\in \exists ^{p}L}
1199:
1163:
1070:
885:
821:
736:
683:
650:
626:
584:
536:
488:
444:
407:
369:
332:
297:
232:
212:
192:
14:
5611:
5555:Probabilistically checkable proof
556:solvable in polynomial time by a
5164:Arora and Barak, 2009, Claim 5.5
4973:In Proceedings of the 13th IEEE
4706:with variables partitioned into
3554:in the hierarchy and a language
3368:of complexity classes including
23:
4648:– 1 alternations of quantifiers
4344: compute the same function
1767: is a polynomial and
1672: is a polynomial and
91:computational complexity theory
5158:
5121:
5096:
5087:
5078:
5069:
5060:
5051:
5042:
4947:. Cambridge University Press.
4666:boolean satisfiability problem
4664:). This is the version of the
4445:
4408:
4207:
4201:
4192:
4186:
3274:Relationships to other classes
2000:
1801:Again, De Morgan's laws hold:
1755:
1660:
1386:
1382:
1374:
1370:
1144:{\displaystyle |w|\leq p(|x|)}
1138:
1134:
1126:
1122:
1112:
1104:
933:
929:
921:
917:
168:
1:
4986:The polynomial-time hierarchy
4929:
3197:corresponds to a collapse of
1178:{\displaystyle \exists ^{p}L}
1085:{\displaystyle \exists ^{p}L}
5590:Structural complexity theory
5048:Arora and Barak, 2009, pp.97
5035:
4990:Theoretical Computer Science
4303:there exists a circuit
109:that generalize the classes
7:
4907:
3988:
3968:{\displaystyle \Sigma _{2}}
3550:: meaning that for a class
3467:-complete problem for some
162:quantified Boolean formulae
133:alternating Turing machines
10:
5616:
5571:List of complexity classes
5143:10.4230/LIPIcs.CSL.2018.22
5066:Arora and Barak, pp.99–100
3683:is a complete problem for
3277:
2522:alternating Turing machine
1151:) witness testifying that
802:, a subset of {0,1}), let
158:polynomial-time reductions
5568:
5527:
5491:
5435:
5328:
5208:
5002:, pp. 409–438.
99:polynomial-time hierarchy
5560:Interactive proof system
4311: with at most
3932:Sipser–Lautemann theorem
2492:play roles analogous to
1092:, and the second string
286:. Then for i ≥ 0 define
32:This article includes a
16:Computer science concept
5084:Arora and Barak, pp.100
5075:Arora and Barak, pp.100
4608:A complete problem for
4172: has at most
61:more precise citations.
5514:Arithmetical hierarchy
4887:– 1 alternations, the
4877:
4843:
4782:
4696:
4636:
4599:
4533:
4488:
4452:
4363:
4223:
4180: gates, and
4023:
3969:
3934:states that the class
3913:
3851:
3778:
3711:
3677:
3650:
3620:
3578:
3542:
3504:
3461:
3405:arithmetical hierarchy
3396:
3345:
3254:
3159:
3079:
3025:
3024:{\displaystyle i>k}
2995:
2941:
2877:
2812:
2725:
2630:
2594:
2556:
2478:arithmetical hierarchy
2467:
2414:
2364:
2291:
2218:
2145:
2090:
2026:
1951:
1873:
1792:
1697:
1585:
1511:
1430:
1257:
1215:
1179:
1145:
1086:
1040:
980:
776:
722:
636:
594:
546:
510:
429:
354:
265:
137:arithmetical hierarchy
97:(sometimes called the
5509:Grzegorczyk hierarchy
5504:Exponential hierarchy
5436:Considered infeasible
4919:Exponential hierarchy
4878:
4844:
4783:
4697:
4637:
4600:
4534:
4489:
4453:
4364:
4328: such that
4224:
4024:
3970:
3914:
3852:
3779:
3712:
3678:
3676:{\displaystyle K_{i}}
3651:
3621:
3579:
3543:
3505:
3462:
3401:exponential hierarchy
3364:
3346:
3255:
3160:
3080:
3026:
3001:, then the hierarchy
2996:
2942:
2878:
2813:
2726:
2628:
2595:
2557:
2468:
2415:
2365:
2292:
2219:
2146:
2091:
2027:
1952:
1874:
1793:
1698:
1595:is the complement of
1586:
1512:
1431:
1258:
1216:
1180:
1146:
1087:
1041:
981:
777:
723:
637:
595:
547:
511:
430:
355:
266:
5499:Polynomial hierarchy
5329:Suspected infeasible
5000:Polynomial hierarchy
4924:Arithmetic hierarchy
4853:
4819:
4730:
4672:
4612:
4559:
4498:
4466:
4375:
4239:
4068:
4032:circuit minimization
3999:
3975:is not contained in
3952:
3944:states that for any
3861:
3788:
3721:
3687:
3660:
3630:
3588:
3558:
3516:
3478:
3437:
3296:
3220:
3177:is also termed as a
3135:
3035:
3009:
3003:collapses to level k
2951:
2891:
2823:
2736:
2649:
2611:, which is equal to
2570:
2532:
2504:, respectively. The
2424:
2377:
2302:
2229:
2164:
2100:
2051:
1961:
1883:
1805:
1708:
1613:
1521:
1447:
1270:
1263:. Similarly, define
1229:
1189:
1159:
1100:
1066:
993:
817:
732:
646:
604:
568:
523:
440:
365:
293:
188:
141:analytical hierarchy
95:polynomial hierarchy
5528:Families of classes
5209:Considered feasible
4872:
4838:
4691:
4631:
4407:
4018:
3880:
3813:
3746:
3706:
3612:
3537:
3499:
3456:
3154:
3074:
3054:
2990:
2970:
2936:
2910:
2872:
2842:
2807:
2781:
2755:
2720:
2694:
2668:
2589:
2551:
2462:
2409:
2359:
2327:
2286:
2254:
2203:
2183:
751:
698:
665:
503:
465:
422:
390:
347:
318:
247:
227:
207:
5600:Complexity classes
5202:Complexity classes
4935:General references
4891:-complete problem
4873:
4856:
4839:
4822:
4778:
4692:
4675:
4632:
4615:
4595:
4529:
4484:
4448:
4391:
4359:
4349:
4219:
4019:
4002:
3965:
3909:
3864:
3847:
3791:
3774:
3724:
3707:
3690:
3673:
3646:
3616:
3594:
3574:
3538:
3519:
3500:
3481:
3457:
3440:
3420:transitive closure
3397:
3341:
3250:
3169:The case in which
3155:
3138:
3075:
3058:
3038:
3021:
2991:
2974:
2954:
2937:
2914:
2894:
2873:
2856:
2826:
2808:
2785:
2759:
2739:
2721:
2698:
2672:
2652:
2631:
2590:
2573:
2552:
2535:
2506:analytic hierarchy
2463:
2446:
2410:
2393:
2360:
2343:
2305:
2287:
2270:
2232:
2214:
2187:
2167:
2141:
2086:
2047:can be defined as
2022:
1947:
1869:
1788:
1693:
1581:
1507:
1426:
1253:
1211:
1185:. In other words,
1175:
1141:
1082:
1036:
976:
772:
735:
718:
682:
649:
632:
590:
542:
506:
487:
443:
425:
406:
368:
350:
331:
296:
261:
231:
211:
191:
145:mathematical logic
107:complexity classes
34:list of references
5577:
5576:
5519:Boolean hierarchy
5492:Class hierarchies
4954:978-0-521-42426-4
4345:
4337:
4329:
4320:
4319: gates
4312:
4304:
4181:
4173:
4035:: given a number
3427:complete problems
3317:
3238:
1768:
1761:
1753:
1673:
1666:
1658:
1332:
1324:
879:
871:
554:decision problems
280:decision problems
177:Oracle definition
87:
86:
79:
5607:
5195:
5188:
5181:
5172:
5171:
5165:
5162:
5156:
5155:
5145:
5125:
5119:
5118:
5100:
5094:
5091:
5085:
5082:
5076:
5073:
5067:
5064:
5058:
5055:
5049:
5046:
5030:
5019:. W.H. Freeman.
5011:David S. Johnson
5007:Michael R. Garey
4996:C. Papadimitriou
4982:L. J. Stockmeyer
4969:L. J. Stockmeyer
4961:
4882:
4880:
4879:
4874:
4871:
4870:
4864:
4848:
4846:
4845:
4840:
4837:
4836:
4830:
4787:
4785:
4784:
4779:
4771:
4770:
4758:
4757:
4745:
4744:
4701:
4699:
4698:
4693:
4690:
4689:
4683:
4641:
4639:
4638:
4633:
4630:
4629:
4623:
4604:
4602:
4601:
4596:
4554:
4546:
4538:
4536:
4535:
4530:
4528:
4527:
4493:
4491:
4490:
4485:
4461:
4457:
4455:
4454:
4449:
4444:
4443:
4437:
4436:
4435:
4425:
4424:
4423:
4406:
4405:
4399:
4387:
4386:
4368:
4366:
4365:
4360:
4358:
4354:
4353:
4350:
4346:
4343:
4338:
4335:
4330:
4327:
4321:
4318:
4313:
4310:
4305:
4302:
4292:
4284:
4283:
4251:
4250:
4228:
4226:
4225:
4220:
4218:
4214:
4213:
4210:
4182:
4179:
4174:
4171:
4161:
4160:
4136:
4135:
4126:
4118:
4117:
4061:
4045:Boolean function
4028:
4026:
4025:
4020:
4017:
4016:
4010:
3974:
3972:
3971:
3966:
3964:
3963:
3942:Kannan's theorem
3926:
3922:
3918:
3916:
3915:
3910:
3908:
3907:
3906:
3894:
3893:
3879:
3878:
3872:
3857:. For instance,
3856:
3854:
3853:
3848:
3846:
3845:
3844:
3843:
3833:
3832:
3812:
3811:
3805:
3783:
3781:
3780:
3775:
3773:
3772:
3771:
3770:
3760:
3759:
3745:
3744:
3738:
3716:
3714:
3713:
3708:
3705:
3704:
3698:
3682:
3680:
3679:
3674:
3672:
3671:
3655:
3653:
3652:
3647:
3645:
3644:
3625:
3623:
3622:
3617:
3611:
3610:
3604:
3603:
3583:
3581:
3580:
3575:
3573:
3572:
3553:
3547:
3545:
3544:
3539:
3536:
3535:
3529:
3528:
3509:
3507:
3506:
3501:
3498:
3497:
3491:
3490:
3466:
3464:
3463:
3458:
3455:
3454:
3448:
3352:
3350:
3348:
3347:
3342:
3340:
3339:
3318:
3310:
3308:
3307:
3287:
3261:
3259:
3257:
3256:
3251:
3249:
3248:
3239:
3231:
3229:
3228:
3211:
3187:the second level
3164:
3162:
3161:
3156:
3153:
3152:
3146:
3084:
3082:
3081:
3076:
3073:
3072:
3066:
3053:
3052:
3046:
3030:
3028:
3027:
3022:
3000:
2998:
2997:
2992:
2989:
2988:
2982:
2969:
2968:
2962:
2946:
2944:
2943:
2938:
2935:
2934:
2928:
2909:
2908:
2902:
2882:
2880:
2879:
2874:
2871:
2870:
2864:
2855:
2854:
2841:
2840:
2834:
2817:
2815:
2814:
2809:
2806:
2805:
2799:
2780:
2779:
2773:
2754:
2753:
2747:
2730:
2728:
2727:
2722:
2719:
2718:
2712:
2693:
2692:
2686:
2667:
2666:
2660:
2599:
2597:
2596:
2591:
2588:
2587:
2581:
2561:
2559:
2558:
2553:
2550:
2549:
2543:
2472:
2470:
2469:
2464:
2461:
2460:
2454:
2442:
2441:
2419:
2417:
2416:
2411:
2408:
2407:
2401:
2389:
2388:
2369:
2367:
2366:
2361:
2358:
2357:
2351:
2342:
2341:
2340:
2326:
2325:
2319:
2296:
2294:
2293:
2288:
2285:
2284:
2278:
2269:
2268:
2267:
2253:
2252:
2246:
2223:
2221:
2220:
2215:
2213:
2212:
2202:
2201:
2195:
2182:
2181:
2175:
2150:
2148:
2147:
2142:
2140:
2139:
2133:
2132:
2131:
2118:
2117:
2095:
2093:
2092:
2087:
2085:
2084:
2078:
2077:
2076:
2063:
2062:
2031:
2029:
2028:
2023:
2021:
2017:
2016:
2015:
2003:
1998:
1997:
1980:
1979:
1973:
1972:
1956:
1954:
1953:
1948:
1946:
1945:
1939:
1938:
1929:
1928:
1927:
1914:
1913:
1907:
1906:
1905:
1895:
1894:
1878:
1876:
1875:
1870:
1868:
1867:
1861:
1860:
1851:
1850:
1849:
1836:
1835:
1829:
1828:
1827:
1817:
1816:
1797:
1795:
1794:
1789:
1787:
1783:
1782:
1781:
1769:
1766:
1759:
1758:
1751:
1747:
1746:
1729:
1728:
1722:
1721:
1720:
1702:
1700:
1699:
1694:
1692:
1688:
1687:
1686:
1674:
1671:
1664:
1663:
1656:
1652:
1651:
1634:
1633:
1627:
1626:
1625:
1605:
1590:
1588:
1587:
1582:
1580:
1579:
1578:
1568:
1567:
1555:
1554:
1553:
1547:
1543:
1539:
1538:
1516:
1514:
1513:
1508:
1506:
1505:
1504:
1494:
1493:
1481:
1480:
1479:
1473:
1469:
1465:
1464:
1441:De Morgan's laws
1435:
1433:
1432:
1427:
1425:
1421:
1420:
1417:
1395:
1391:
1390:
1389:
1385:
1377:
1330:
1322:
1321:
1320:
1282:
1281:
1262:
1260:
1259:
1254:
1220:
1218:
1217:
1212:
1207:
1206:
1184:
1182:
1181:
1176:
1171:
1170:
1150:
1148:
1147:
1142:
1137:
1129:
1115:
1107:
1091:
1089:
1088:
1083:
1078:
1077:
1045:
1043:
1042:
1037:
1035:
1034:
985:
983:
982:
977:
972:
968:
967:
964:
942:
938:
937:
936:
932:
924:
877:
869:
868:
867:
829:
828:
805:
800:decision problem
793:
781:
779:
778:
773:
771:
770:
769:
768:
750:
749:
743:
727:
725:
724:
719:
717:
716:
697:
696:
690:
678:
677:
664:
663:
657:
641:
639:
638:
633:
631:
630:
629:
623:
622:
599:
597:
596:
591:
589:
588:
587:
581:
580:
560:augmented by an
551:
549:
548:
543:
541:
540:
539:
533:
532:
515:
513:
512:
507:
505:
504:
502:
501:
495:
485:
484:
464:
463:
457:
434:
432:
431:
426:
424:
423:
421:
420:
414:
404:
403:
389:
388:
382:
359:
357:
356:
351:
349:
348:
346:
345:
339:
329:
328:
317:
316:
310:
270:
268:
267:
262:
257:
256:
246:
245:
239:
226:
225:
219:
206:
205:
199:
82:
75:
71:
68:
62:
57:this article by
48:inline citations
27:
26:
19:
5615:
5614:
5610:
5609:
5608:
5606:
5605:
5604:
5580:
5579:
5578:
5573:
5564:
5523:
5487:
5431:
5425:PSPACE-complete
5324:
5204:
5199:
5169:
5168:
5163:
5159:
5126:
5122:
5115:
5101:
5097:
5092:
5088:
5083:
5079:
5074:
5070:
5065:
5061:
5056:
5052:
5047:
5043:
5038:
5027:
4955:
4937:
4932:
4910:
4905:
4900:this Compendium
4866:
4865:
4860:
4854:
4851:
4850:
4832:
4831:
4826:
4820:
4817:
4816:
4810:
4803:
4796:
4766:
4762:
4753:
4749:
4740:
4736:
4731:
4728:
4727:
4722:
4716:
4685:
4684:
4679:
4673:
4670:
4669:
4662:
4655:
4625:
4624:
4619:
4613:
4610:
4609:
4560:
4557:
4556:
4552:
4544:
4539:if and only if
4520:
4519:
4499:
4496:
4495:
4467:
4464:
4463:
4459:
4439:
4438:
4431:
4430:
4426:
4419:
4418:
4414:
4401:
4400:
4395:
4379:
4378:
4376:
4373:
4372:
4348:
4347:
4342:
4336: and
4334:
4326:
4323:
4322:
4317:
4309:
4301:
4297:
4293:
4288:
4279:
4278:
4259:
4255:
4243:
4242:
4240:
4237:
4236:
4178:
4170:
4166:
4162:
4156:
4152:
4131:
4130:
4122:
4113:
4112:
4081:
4077:
4069:
4066:
4065:
4059:
4012:
4011:
4006:
4000:
3997:
3996:
3991:
3959:
3955:
3953:
3950:
3949:
3924:
3920:
3896:
3895:
3886:
3885:
3884:
3874:
3873:
3868:
3862:
3859:
3858:
3839:
3835:
3834:
3819:
3818:
3817:
3807:
3806:
3795:
3789:
3786:
3785:
3766:
3762:
3761:
3752:
3751:
3750:
3740:
3739:
3728:
3722:
3719:
3718:
3700:
3699:
3694:
3688:
3685:
3684:
3667:
3663:
3661:
3658:
3657:
3640:
3639:
3631:
3628:
3627:
3606:
3605:
3599:
3598:
3589:
3586:
3585:
3568:
3567:
3559:
3556:
3555:
3551:
3531:
3530:
3524:
3523:
3517:
3514:
3513:
3493:
3492:
3486:
3485:
3479:
3476:
3475:
3450:
3449:
3444:
3438:
3435:
3434:
3431:PSPACE-complete
3359:
3358:
3353:
3320:
3319:
3309:
3300:
3299:
3297:
3294:
3293:
3291:
3289:
3282:
3276:
3268:
3267:
3262:
3241:
3240:
3230:
3224:
3223:
3221:
3218:
3217:
3215:
3213:
3148:
3147:
3142:
3136:
3133:
3132:
3098:if and only if
3068:
3067:
3062:
3048:
3047:
3042:
3036:
3033:
3032:
3010:
3007:
3006:
2984:
2983:
2978:
2964:
2963:
2958:
2952:
2949:
2948:
2930:
2929:
2918:
2904:
2903:
2898:
2892:
2889:
2888:
2866:
2865:
2860:
2847:
2846:
2836:
2835:
2830:
2824:
2821:
2820:
2801:
2800:
2789:
2775:
2774:
2763:
2749:
2748:
2743:
2737:
2734:
2733:
2714:
2713:
2702:
2688:
2687:
2676:
2662:
2661:
2656:
2650:
2647:
2646:
2623:
2583:
2582:
2577:
2571:
2568:
2567:
2545:
2544:
2539:
2533:
2530:
2529:
2518:
2456:
2455:
2450:
2428:
2427:
2425:
2422:
2421:
2403:
2402:
2397:
2381:
2380:
2378:
2375:
2374:
2353:
2352:
2347:
2336:
2335:
2331:
2321:
2320:
2309:
2303:
2300:
2299:
2280:
2279:
2274:
2263:
2262:
2258:
2248:
2247:
2236:
2230:
2227:
2226:
2208:
2207:
2197:
2196:
2191:
2177:
2176:
2171:
2165:
2162:
2161:
2135:
2134:
2127:
2126:
2122:
2104:
2103:
2101:
2098:
2097:
2080:
2079:
2072:
2071:
2067:
2055:
2054:
2052:
2049:
2048:
2011:
2010:
1999:
1993:
1989:
1988:
1984:
1975:
1974:
1965:
1964:
1962:
1959:
1958:
1941:
1940:
1931:
1930:
1923:
1922:
1918:
1909:
1908:
1901:
1900:
1896:
1887:
1886:
1884:
1881:
1880:
1863:
1862:
1853:
1852:
1845:
1844:
1840:
1831:
1830:
1823:
1822:
1818:
1809:
1808:
1806:
1803:
1802:
1777:
1776:
1765:
1754:
1742:
1738:
1737:
1733:
1724:
1723:
1716:
1715:
1711:
1709:
1706:
1705:
1682:
1681:
1670:
1659:
1647:
1643:
1642:
1638:
1629:
1628:
1621:
1620:
1616:
1614:
1611:
1610:
1603:
1574:
1573:
1569:
1563:
1559:
1549:
1548:
1534:
1530:
1529:
1525:
1524:
1522:
1519:
1518:
1500:
1499:
1495:
1489:
1485:
1475:
1474:
1460:
1456:
1455:
1451:
1450:
1448:
1445:
1444:
1381:
1373:
1363:
1359:
1337:
1333:
1329:
1325:
1316:
1312:
1293:
1289:
1277:
1273:
1271:
1268:
1267:
1230:
1227:
1226:
1202:
1198:
1190:
1187:
1186:
1166:
1162:
1160:
1157:
1156:
1155:is a member of
1133:
1125:
1111:
1103:
1101:
1098:
1097:
1073:
1069:
1067:
1064:
1063:
1062:is a member of
1030:
1026:
994:
991:
990:
928:
920:
910:
906:
884:
880:
876:
872:
863:
859:
840:
836:
824:
820:
818:
815:
814:
803:
791:
788:
761:
757:
756:
755:
745:
744:
739:
733:
730:
729:
703:
702:
692:
691:
686:
670:
669:
659:
658:
653:
647:
644:
643:
625:
624:
609:
608:
607:
605:
602:
601:
583:
582:
573:
572:
571:
569:
566:
565:
535:
534:
528:
527:
526:
524:
521:
520:
497:
496:
491:
486:
471:
470:
469:
459:
458:
447:
441:
438:
437:
416:
415:
410:
405:
396:
395:
394:
384:
383:
372:
366:
363:
362:
341:
340:
335:
330:
324:
323:
322:
312:
311:
300:
294:
291:
290:
284:polynomial time
252:
251:
241:
240:
235:
221:
220:
215:
201:
200:
195:
189:
186:
185:
179:
171:
129:oracle machines
83:
72:
66:
63:
52:
38:related reading
28:
24:
17:
12:
11:
5:
5613:
5603:
5602:
5597:
5592:
5575:
5574:
5569:
5566:
5565:
5563:
5562:
5557:
5552:
5547:
5542:
5537:
5531:
5529:
5525:
5524:
5522:
5521:
5516:
5511:
5506:
5501:
5495:
5493:
5489:
5488:
5486:
5485:
5480:
5475:
5470:
5465:
5460:
5455:
5450:
5445:
5439:
5437:
5433:
5432:
5430:
5429:
5428:
5427:
5417:
5412:
5411:
5410:
5400:
5395:
5390:
5385:
5380:
5375:
5370:
5365:
5364:
5363:
5361:co-NP-complete
5358:
5353:
5348:
5338:
5332:
5330:
5326:
5325:
5323:
5322:
5317:
5312:
5307:
5302:
5297:
5292:
5291:
5290:
5280:
5275:
5270:
5265:
5264:
5263:
5253:
5248:
5243:
5238:
5233:
5228:
5223:
5218:
5212:
5210:
5206:
5205:
5198:
5197:
5190:
5183:
5175:
5167:
5166:
5157:
5120:
5113:
5095:
5086:
5077:
5068:
5059:
5050:
5040:
5039:
5037:
5034:
5033:
5032:
5025:
5003:
4993:
4979:
4962:
4953:
4936:
4933:
4931:
4928:
4927:
4926:
4921:
4916:
4909:
4906:
4904:
4903:
4896:
4869:
4863:
4859:
4835:
4829:
4825:
4808:
4801:
4794:
4789:
4788:
4777:
4774:
4769:
4765:
4761:
4756:
4752:
4748:
4743:
4739:
4735:
4720:
4714:
4688:
4682:
4678:
4660:
4653:
4628:
4622:
4618:
4606:
4594:
4591:
4588:
4585:
4582:
4579:
4576:
4573:
4570:
4567:
4564:
4526:
4523:
4518:
4515:
4512:
4509:
4506:
4503:
4483:
4480:
4477:
4474:
4471:
4447:
4442:
4434:
4429:
4422:
4417:
4413:
4410:
4404:
4398:
4394:
4390:
4385:
4382:
4370:
4369:
4357:
4352:
4341:
4333:
4325:
4324:
4316:
4308:
4300:
4299:
4296:
4291:
4287:
4282:
4277:
4274:
4271:
4268:
4265:
4262:
4258:
4254:
4249:
4246:
4230:
4229:
4217:
4212:
4209:
4206:
4203:
4200:
4197:
4194:
4191:
4188:
4185:
4177:
4169:
4165:
4159:
4155:
4151:
4148:
4145:
4142:
4139:
4134:
4129:
4125:
4121:
4116:
4111:
4108:
4105:
4102:
4099:
4096:
4093:
4090:
4087:
4084:
4080:
4076:
4073:
4039:and a circuit
4015:
4009:
4005:
3992:
3990:
3987:
3983:Toda's theorem
3962:
3958:
3905:
3902:
3899:
3892:
3889:
3883:
3877:
3871:
3867:
3842:
3838:
3831:
3828:
3825:
3822:
3816:
3810:
3804:
3801:
3798:
3794:
3769:
3765:
3758:
3755:
3749:
3743:
3737:
3734:
3731:
3727:
3703:
3697:
3693:
3670:
3666:
3643:
3638:
3635:
3615:
3609:
3602:
3597:
3593:
3571:
3566:
3563:
3534:
3527:
3522:
3496:
3489:
3484:
3453:
3447:
3443:
3354:
3338:
3335:
3332:
3329:
3326:
3323:
3316:
3313:
3306:
3303:
3290:
3284:
3275:
3272:
3263:
3247:
3244:
3237:
3234:
3227:
3214:
3208:
3167:
3166:
3151:
3145:
3141:
3107:
3071:
3065:
3061:
3057:
3051:
3045:
3041:
3020:
3017:
3014:
2987:
2981:
2977:
2973:
2967:
2961:
2957:
2933:
2927:
2924:
2921:
2917:
2913:
2907:
2901:
2897:
2884:
2883:
2869:
2863:
2859:
2853:
2850:
2845:
2839:
2833:
2829:
2818:
2804:
2798:
2795:
2792:
2788:
2784:
2778:
2772:
2769:
2766:
2762:
2758:
2752:
2746:
2742:
2731:
2717:
2711:
2708:
2705:
2701:
2697:
2691:
2685:
2682:
2679:
2675:
2671:
2665:
2659:
2655:
2622:
2619:
2586:
2580:
2576:
2548:
2542:
2538:
2517:
2514:
2459:
2453:
2449:
2445:
2440:
2437:
2434:
2431:
2406:
2400:
2396:
2392:
2387:
2384:
2371:
2370:
2356:
2350:
2346:
2339:
2334:
2330:
2324:
2318:
2315:
2312:
2308:
2297:
2283:
2277:
2273:
2266:
2261:
2257:
2251:
2245:
2242:
2239:
2235:
2224:
2211:
2206:
2200:
2194:
2190:
2186:
2180:
2174:
2170:
2138:
2130:
2125:
2121:
2116:
2113:
2110:
2107:
2083:
2075:
2070:
2066:
2061:
2058:
2020:
2014:
2009:
2006:
2002:
1996:
1992:
1987:
1983:
1978:
1971:
1968:
1944:
1937:
1934:
1926:
1921:
1917:
1912:
1904:
1899:
1893:
1890:
1866:
1859:
1856:
1848:
1843:
1839:
1834:
1826:
1821:
1815:
1812:
1799:
1798:
1786:
1780:
1775:
1772:
1764:
1757:
1750:
1745:
1741:
1736:
1732:
1727:
1719:
1714:
1703:
1691:
1685:
1680:
1677:
1669:
1662:
1655:
1650:
1646:
1641:
1637:
1632:
1624:
1619:
1577:
1572:
1566:
1562:
1558:
1552:
1546:
1542:
1537:
1533:
1528:
1503:
1498:
1492:
1488:
1484:
1478:
1472:
1468:
1463:
1459:
1454:
1437:
1436:
1424:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1394:
1388:
1384:
1380:
1376:
1372:
1369:
1366:
1362:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1336:
1328:
1319:
1315:
1311:
1308:
1305:
1302:
1299:
1296:
1292:
1288:
1285:
1280:
1276:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1210:
1205:
1201:
1197:
1194:
1174:
1169:
1165:
1140:
1136:
1132:
1128:
1124:
1121:
1118:
1114:
1110:
1106:
1096:is a "short" (
1081:
1076:
1072:
1033:
1029:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
987:
986:
975:
971:
966:
963:
960:
957:
954:
951:
948:
945:
941:
935:
931:
927:
923:
919:
916:
913:
909:
905:
902:
899:
896:
893:
890:
887:
883:
875:
866:
862:
858:
855:
852:
849:
846:
843:
839:
835:
832:
827:
823:
787:
784:
767:
764:
760:
754:
748:
742:
738:
715:
712:
709:
706:
701:
695:
689:
685:
681:
676:
673:
668:
662:
656:
652:
628:
621:
618:
615:
612:
586:
579:
576:
558:Turing machine
552:is the set of
538:
531:
517:
516:
500:
494:
490:
483:
480:
477:
474:
468:
462:
456:
453:
450:
446:
435:
419:
413:
409:
402:
399:
393:
387:
381:
378:
375:
371:
360:
344:
338:
334:
327:
321:
315:
309:
306:
303:
299:
278:is the set of
272:
271:
260:
255:
250:
244:
238:
234:
230:
224:
218:
214:
210:
204:
198:
194:
178:
175:
170:
167:
160:) that ask if
85:
84:
42:external links
31:
29:
22:
15:
9:
6:
4:
3:
2:
5612:
5601:
5598:
5596:
5593:
5591:
5588:
5587:
5585:
5572:
5567:
5561:
5558:
5556:
5553:
5551:
5548:
5546:
5543:
5541:
5538:
5536:
5533:
5532:
5530:
5526:
5520:
5517:
5515:
5512:
5510:
5507:
5505:
5502:
5500:
5497:
5496:
5494:
5490:
5484:
5481:
5479:
5476:
5474:
5471:
5469:
5466:
5464:
5461:
5459:
5456:
5454:
5451:
5449:
5446:
5444:
5441:
5440:
5438:
5434:
5426:
5423:
5422:
5421:
5418:
5416:
5413:
5409:
5406:
5405:
5404:
5401:
5399:
5396:
5394:
5391:
5389:
5386:
5384:
5381:
5379:
5376:
5374:
5371:
5369:
5366:
5362:
5359:
5357:
5354:
5352:
5349:
5347:
5344:
5343:
5342:
5339:
5337:
5334:
5333:
5331:
5327:
5321:
5318:
5316:
5313:
5311:
5308:
5306:
5303:
5301:
5298:
5296:
5293:
5289:
5286:
5285:
5284:
5281:
5279:
5276:
5274:
5271:
5269:
5266:
5262:
5259:
5258:
5257:
5254:
5252:
5249:
5247:
5244:
5242:
5239:
5237:
5234:
5232:
5229:
5227:
5224:
5222:
5219:
5217:
5214:
5213:
5211:
5207:
5203:
5196:
5191:
5189:
5184:
5182:
5177:
5176:
5173:
5161:
5153:
5149:
5144:
5139:
5135:
5131:
5124:
5116:
5114:9781351644051
5110:
5106:
5099:
5090:
5081:
5072:
5063:
5054:
5045:
5041:
5028:
5026:0-7167-1045-5
5022:
5018:
5017:
5012:
5008:
5004:
5001:
4997:
4994:
4991:
4987:
4983:
4980:
4977:
4976:
4970:
4966:
4963:
4960:
4956:
4950:
4946:
4945:
4939:
4938:
4925:
4922:
4920:
4917:
4915:
4912:
4911:
4901:
4897:
4894:
4890:
4886:
4861:
4827:
4814:
4807:
4800:
4793:
4775:
4772:
4767:
4763:
4754:
4750:
4741:
4737:
4726:
4725:
4723:
4713:
4709:
4705:
4680:
4667:
4663:
4656:
4650:(abbreviated
4649:
4647:
4620:
4607:
4592:
4589:
4583:
4580:
4577:
4574:
4571:
4568:
4565:
4550:
4542:
4516:
4510:
4507:
4504:
4478:
4475:
4472:
4411:
4396:
4388:
4355:
4339:
4331:
4314:
4306:
4294:
4285:
4275:
4269:
4266:
4263:
4256:
4252:
4235:
4234:
4233:
4215:
4204:
4198:
4195:
4189:
4183:
4175:
4167:
4163:
4157:
4149:
4146:
4143:
4137:
4127:
4119:
4109:
4103:
4100:
4097:
4094:
4091:
4088:
4085:
4078:
4074:
4071:
4064:
4063:
4057:
4053:
4049:
4046:
4042:
4038:
4034:
4033:
4007:
3994:
3993:
3986:
3984:
3980:
3978:
3960:
3947:
3943:
3939:
3937:
3933:
3928:
3881:
3869:
3840:
3836:
3814:
3802:
3799:
3796:
3767:
3763:
3747:
3735:
3732:
3729:
3695:
3668:
3664:
3636:
3633:
3613:
3595:
3591:
3564:
3561:
3549:
3520:
3512:closed under
3482:
3472:
3470:
3445:
3432:
3428:
3423:
3421:
3417:
3413:
3408:
3406:
3402:
3395:
3391:
3387:
3383:
3379:
3375:
3371:
3367:
3366:Hasse diagram
3363:
3357:
3314:
3311:
3281:
3271:
3266:
3235:
3232:
3206:
3204:
3200:
3196:
3192:
3188:
3184:
3180:
3176:
3172:
3143:
3130:
3126:
3122:
3118:
3117:
3112:
3108:
3105:
3101:
3097:
3096:
3092:
3088:
3087:
3086:
3063:
3055:
3043:
3018:
3015:
3012:
3004:
2979:
2971:
2959:
2925:
2922:
2919:
2911:
2899:
2861:
2843:
2831:
2819:
2796:
2793:
2790:
2782:
2770:
2767:
2764:
2756:
2744:
2732:
2709:
2706:
2703:
2695:
2683:
2680:
2677:
2669:
2657:
2645:
2644:
2643:
2640:
2638:
2637:
2627:
2618:
2616:
2615:
2610:
2606:
2601:
2578:
2565:
2540:
2526:
2523:
2513:
2511:
2507:
2503:
2502:
2497:
2496:
2491:
2490:
2485:
2484:
2479:
2474:
2451:
2443:
2398:
2390:
2348:
2328:
2316:
2313:
2310:
2298:
2275:
2255:
2243:
2240:
2237:
2225:
2204:
2192:
2184:
2172:
2160:
2159:
2158:
2156:
2155:
2119:
2064:
2046:
2045:
2040:
2039:
2033:
2018:
2007:
2004:
1994:
1990:
1985:
1981:
1915:
1837:
1784:
1773:
1770:
1762:
1748:
1743:
1734:
1730:
1704:
1689:
1678:
1675:
1667:
1653:
1648:
1639:
1635:
1609:
1608:
1607:
1600:
1598:
1594:
1570:
1564:
1556:
1544:
1540:
1535:
1526:
1496:
1490:
1482:
1470:
1466:
1461:
1452:
1442:
1422:
1414:
1411:
1405:
1402:
1399:
1392:
1378:
1367:
1364:
1356:
1353:
1350:
1344:
1341:
1334:
1326:
1317:
1309:
1306:
1303:
1297:
1294:
1290:
1286:
1283:
1278:
1266:
1265:
1264:
1250:
1247:
1241:
1238:
1235:
1224:
1208:
1203:
1195:
1192:
1172:
1167:
1154:
1130:
1119:
1116:
1108:
1095:
1079:
1074:
1061:
1057:
1053:
1049:
1031:
1023:
1020:
1017:
1011:
1005:
1002:
999:
973:
969:
961:
958:
952:
949:
946:
939:
925:
914:
911:
903:
900:
897:
891:
888:
881:
873:
864:
856:
853:
850:
844:
841:
837:
833:
830:
825:
813:
812:
811:
810:, and define
809:
801:
797:
783:
752:
740:
699:
687:
679:
666:
654:
563:
559:
555:
492:
466:
454:
451:
448:
436:
411:
391:
379:
376:
373:
361:
336:
319:
307:
304:
301:
289:
288:
287:
285:
281:
277:
258:
248:
236:
228:
216:
208:
196:
184:
183:
182:
174:
166:
163:
159:
154:
152:
151:
146:
142:
138:
134:
130:
126:
125:
120:
119:
114:
113:
108:
104:
100:
96:
92:
81:
78:
70:
60:
56:
50:
49:
43:
39:
35:
30:
21:
20:
5498:
5160:
5133:
5123:
5104:
5098:
5089:
5080:
5071:
5062:
5053:
5044:
5014:
4999:
4989:
4972:
4958:
4943:
4888:
4884:
4812:
4805:
4798:
4791:
4718:
4711:
4707:
4703:
4658:
4651:
4645:
4643:
4548:
4541:there exists
4540:
4231:
4055:
4051:
4047:
4043:computing a
4040:
4036:
4030:
3981:
3976:
3945:
3940:
3929:
3511:
3473:
3468:
3424:
3409:
3398:
3269:
3202:
3198:
3194:
3190:
3186:
3182:
3178:
3174:
3170:
3168:
3128:
3124:
3120:
3114:
3110:
3103:
3099:
3094:
3090:
3002:
2947:, or if any
2885:
2641:
2634:
2632:
2612:
2608:
2604:
2602:
2563:
2527:
2519:
2510:real numbers
2499:
2493:
2487:
2481:
2475:
2372:
2152:
2042:
2036:
2035:The classes
2034:
1800:
1601:
1596:
1592:
1438:
1222:
1152:
1093:
1059:
1055:
1051:
1047:
988:
789:
518:
282:solvable in
273:
180:
172:
155:
148:
122:
116:
110:
98:
94:
88:
73:
64:
53:Please help
45:
5408:#P-complete
5346:NP-complete
5261:NL-complete
4965:A. R. Meyer
3548:-reductions
3189:. The case
169:Definitions
59:introducing
5584:Categories
5463:ELEMENTARY
5288:P-complete
4930:References
4547:such that
4543:a circuit
3278:See also:
3005:: for all
2528:We define
2373:Note that
1439:Note that
1225:such that
808:polynomial
5595:Hierarchy
5458:2-EXPTIME
5036:Citations
4858:Π
4824:Σ
4773:…
4760:∃
4747:∀
4734:∃
4677:Σ
4617:Σ
4590:∈
4587:⟩
4563:⟨
4517:∈
4514:⟩
4502:⟨
4482:⟩
4470:⟨
4428:∀
4416:∃
4393:Σ
4389:∈
4286:×
4276:∈
4273:⟩
4261:⟨
4158:∗
4138:×
4128:×
4120:×
4110:∈
4107:⟩
4083:⟨
4004:Σ
3957:Σ
3866:Σ
3793:Π
3726:Σ
3692:Σ
3637:∈
3596:≤
3565:∈
3521:≤
3483:≤
3442:Σ
3140:Π
3060:Σ
3040:Σ
2976:Π
2956:Σ
2916:Σ
2896:Σ
2858:Π
2828:Σ
2787:Π
2783:⊆
2761:Δ
2757:⊆
2741:Π
2700:Σ
2696:⊆
2674:Δ
2670:⊆
2654:Σ
2575:Π
2537:Σ
2448:Π
2395:Σ
2345:Σ
2333:∀
2307:Π
2272:Π
2260:∃
2234:Σ
2189:Π
2169:Σ
2124:∀
2069:∃
2008:∈
1920:∃
1898:∀
1842:∀
1820:∃
1774:∈
1740:∀
1713:∀
1679:∈
1645:∃
1618:∃
1561:∃
1532:∀
1487:∀
1458:∃
1412:∈
1409:⟩
1397:⟨
1365:≤
1345:∈
1339:∀
1318:∗
1298:∈
1275:∀
1248:∈
1245:⟩
1233:⟨
1200:∃
1196:∈
1164:∃
1117:≤
1071:∃
1032:∗
1012:∈
1009:⟩
997:⟨
959:∈
956:⟩
944:⟨
912:≤
892:∈
886:∃
865:∗
845:∈
822:∃
737:Δ
684:Π
651:Σ
489:Σ
445:Π
408:Σ
370:Σ
333:Σ
298:Δ
233:Π
213:Σ
193:Δ
103:hierarchy
67:July 2019
5453:EXPSPACE
5448:NEXPTIME
5216:DLOGTIME
5013:(1979).
4908:See also
4458:because
3989:Problems
3179:collapse
2480:, where
2151:, where
1957:, where
1591:, where
798:(i.e. a
796:language
5443:EXPTIME
5351:NP-hard
5152:4903744
4914:EXPTIME
4717:, ...,
4551:inputs
4549:for all
3717:, then
3626:, then
3351:
3292:
3260:
3216:
3181:of the
101:) is a
55:improve
5550:NSPACE
5545:DSPACE
5420:PSPACE
5150:
5111:
5023:
4951:
4889:PSPACE
4811:, ...
4058:. Let
3784:, and
3412:PSPACE
3394:PSPACE
3392:, and
3386:P/poly
2614:PSPACE
2420:, and
2096:, and
1760:
1752:
1665:
1657:
1443:hold:
1331:
1323:
989:where
878:
870:
728:, and
562:oracle
519:where
274:where
124:PSPACE
93:, the
5540:NTIME
5535:DTIME
5356:co-NP
5148:S2CID
4710:sets
3979:(n).
3584:, if
3378:co-NP
3129:co-NP
3119:then
3116:co-NP
2044:co-NP
806:be a
794:be a
143:from
118:co-NP
40:, or
5368:TFNP
5109:ISBN
5021:ISBN
5009:and
4967:and
4949:ISBN
4893:TQBF
4668:for
4659:QSAT
3977:SIZE
3930:The
3403:and
3016:>
2498:and
2486:and
2041:and
1879:and
1602:Let
1517:and
1050:and
600:and
139:and
115:and
5483:ALL
5383:QMA
5373:FNP
5315:APX
5310:BQP
5305:BPP
5295:ZPP
5226:ACC
5138:doi
4657:or
4652:QBF
4642:is
4029:is
3936:BPP
3382:BPP
3201:to
3185:to
3131:is
3127:. (
3109:If
2520:An
131:or
105:of
89:In
5586::
5478:RE
5468:PR
5415:IP
5403:#P
5398:PP
5393:⊕P
5388:PH
5378:AM
5341:NP
5336:UP
5320:FP
5300:RP
5278:CC
5273:SC
5268:NC
5256:NL
5251:FL
5246:RL
5241:SL
5231:TC
5221:AC
5146:.
5132:.
4988:.
4984:.
4957:.
4555:,
4494:,
3948:,
3471:.
3407:.
3390:PH
3388:,
3384:,
3380:,
3376:,
3374:NP
3372:,
3205:.
3199:PH
3195:NP
3193:=
3183:PH
3175:PH
3173:=
3171:NP
3165:.)
3125:PH
3123:=
3121:NP
3113:=
3111:NP
3104:PH
3102:=
3095:NP
3093:=
3031:,
2639:.
2636:PH
2617:.
2609:AP
2512:.
2501:NP
2489:RE
2473:.
2329::=
2256::=
2205::=
2185::=
2038:NP
2032:.
1731::=
1636::=
1599:.
1287::=
834::=
467::=
392::=
320::=
249::=
229::=
209::=
153:.
150:PH
112:NP
44:,
36:,
5473:R
5283:P
5236:L
5194:e
5187:t
5180:v
5154:.
5140::
5117:.
5029:.
4902:.
4895:.
4885:k
4868:P
4862:k
4834:P
4828:k
4813:f
4809:3
4806:X
4802:2
4799:X
4795:1
4792:X
4776:f
4768:3
4764:X
4755:2
4751:X
4742:1
4738:X
4721:k
4719:X
4715:1
4712:X
4708:k
4704:f
4687:P
4681:k
4661:k
4654:k
4646:k
4627:P
4621:k
4605:.
4593:L
4584:x
4581:,
4578:B
4575:,
4572:k
4569:,
4566:A
4553:x
4545:B
4525:M
4522:C
4511:k
4508:,
4505:A
4479:k
4476:,
4473:A
4460:L
4446:)
4441:P
4433:P
4421:P
4412:=
4409:(
4403:P
4397:2
4384:M
4381:C
4356:}
4340:B
4332:A
4315:k
4307:B
4295:|
4290:N
4281:C
4270:k
4267:,
4264:A
4257:{
4253:=
4248:M
4245:C
4216:}
4208:)
4205:x
4202:(
4199:B
4196:=
4193:)
4190:x
4187:(
4184:A
4176:k
4168:B
4164:|
4154:}
4150:1
4147:,
4144:0
4141:{
4133:C
4124:N
4115:C
4104:x
4101:,
4098:B
4095:,
4092:k
4089:,
4086:A
4079:{
4075:=
4072:L
4060:C
4056:f
4052:k
4048:f
4041:A
4037:k
4014:P
4008:2
3961:2
3946:k
3925:C
3921:C
3904:T
3901:A
3898:S
3891:P
3888:N
3882:=
3876:P
3870:2
3841:i
3837:K
3830:P
3827:N
3824:o
3821:c
3815:=
3809:P
3803:1
3800:+
3797:i
3768:i
3764:K
3757:P
3754:N
3748:=
3742:P
3736:1
3733:+
3730:i
3702:P
3696:i
3669:i
3665:K
3642:C
3634:A
3614:L
3608:P
3601:m
3592:A
3570:C
3562:L
3552:C
3533:P
3526:m
3495:P
3488:m
3469:k
3452:P
3446:k
3370:P
3337:E
3334:C
3331:A
3328:P
3325:S
3322:P
3315:?
3312:=
3305:H
3302:P
3288::
3246:P
3243:N
3236:?
3233:=
3226:P
3212::
3203:P
3191:P
3150:P
3144:1
3106:.
3100:P
3091:P
3070:P
3064:k
3056:=
3050:P
3044:i
3019:k
3013:i
2986:P
2980:k
2972:=
2966:P
2960:k
2932:P
2926:1
2923:+
2920:k
2912:=
2906:P
2900:k
2868:P
2862:i
2852:o
2849:c
2844:=
2838:P
2832:i
2803:P
2797:1
2794:+
2791:i
2777:P
2771:1
2768:+
2765:i
2751:P
2745:i
2716:P
2710:1
2707:+
2704:i
2690:P
2684:1
2681:+
2678:i
2664:P
2658:i
2605:k
2585:P
2579:k
2564:k
2547:P
2541:k
2495:P
2483:R
2458:P
2452:1
2444:=
2439:P
2436:N
2433:o
2430:c
2405:P
2399:1
2391:=
2386:P
2383:N
2355:P
2349:k
2338:P
2323:P
2317:1
2314:+
2311:k
2282:P
2276:k
2265:P
2250:P
2244:1
2241:+
2238:k
2210:P
2199:P
2193:0
2179:P
2173:0
2154:P
2137:P
2129:P
2120:=
2115:P
2112:N
2109:o
2106:c
2082:P
2074:P
2065:=
2060:P
2057:N
2019:}
2013:C
2005:L
2001:|
1995:c
1991:L
1986:{
1982:=
1977:C
1970:o
1967:c
1943:C
1936:o
1933:c
1925:P
1916:=
1911:C
1903:P
1892:o
1889:c
1865:C
1858:o
1855:c
1847:P
1838:=
1833:C
1825:P
1814:o
1811:c
1785:}
1779:C
1771:L
1763:p
1756:|
1749:L
1744:p
1735:{
1726:C
1718:P
1690:}
1684:C
1676:L
1668:p
1661:|
1654:L
1649:p
1640:{
1631:C
1623:P
1604:C
1597:L
1593:L
1576:c
1571:L
1565:p
1557:=
1551:c
1545:)
1541:L
1536:p
1527:(
1502:c
1497:L
1491:p
1483:=
1477:c
1471:)
1467:L
1462:p
1453:(
1423:}
1415:L
1406:w
1403:,
1400:x
1393:)
1387:)
1383:|
1379:x
1375:|
1371:(
1368:p
1361:}
1357:1
1354:,
1351:0
1348:{
1342:w
1335:(
1327:|
1314:}
1310:1
1307:,
1304:0
1301:{
1295:x
1291:{
1284:L
1279:p
1251:L
1242:w
1239:,
1236:x
1223:w
1209:L
1204:p
1193:x
1173:L
1168:p
1153:x
1139:)
1135:|
1131:x
1127:|
1123:(
1120:p
1113:|
1109:w
1105:|
1094:w
1080:L
1075:p
1060:x
1056:L
1052:w
1048:x
1028:}
1024:1
1021:,
1018:0
1015:{
1006:w
1003:,
1000:x
974:,
970:}
962:L
953:w
950:,
947:x
940:)
934:)
930:|
926:x
922:|
918:(
915:p
908:}
904:1
901:,
898:0
895:{
889:w
882:(
874:|
861:}
857:1
854:,
851:0
848:{
842:x
838:{
831:L
826:p
804:p
792:L
766:P
763:N
759:P
753:=
747:P
741:2
714:P
711:N
708:o
705:c
700:=
694:P
688:1
680:,
675:P
672:N
667:=
661:P
655:1
627:A
620:P
617:N
614:o
611:c
585:A
578:P
575:N
537:A
530:P
499:P
493:i
482:P
479:N
476:o
473:c
461:P
455:1
452:+
449:i
418:P
412:i
401:P
398:N
386:P
380:1
377:+
374:i
343:P
337:i
326:P
314:P
308:1
305:+
302:i
276:P
259:,
254:P
243:P
237:0
223:P
217:0
203:P
197:0
80:)
74:(
69:)
65:(
51:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.