1066:
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
429:
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,
293:
Suppose that polynomial sized circuits for SAT not only exist, but also that they could be constructed by a polynomial time algorithm. Then this supposition implies that SAT itself could be solved by a polynomial time algorithm that constructs the circuit and then applies it. That is, efficiently
656:. Once these two smaller instances have been constructed, apply the test for solvability to each of them. If one of these two tests returns that the smaller instance is satisfiable, continue solving that instance until a complete solution has been derived.
3911:
836:
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
2142:
3832:
2908:
4050:
2797:
2049:
2654:
2354:
2545:
2258:
3702:
612:
Self-reducibility describes the phenomenon that, if we can quickly test whether a SAT instance is solvable, we can almost as quickly find an explicit solution to the instance. To find a solution to an instance
3524:
4138:
3766:
3640:
1053:
3271:
3055:
1389:
1216:
153:
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
3439:
3206:
3141:
1110:
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
3331:
1685:
811:
3964:
1590:
404:
132:
1766:
922:
3582:
3371:
2407:
1442:
88:
1108:
1827:
4295:
3843:
1147:
2997:
1904:
862:
455:
353:
322:
232:
201:
1969:
1934:
1857:
1308:
754:
708:
603:
494:
2065:
2684:
2434:
1509:
1473:
1274:
1243:
961:
834:
427:
2970:
2931:
1877:
3777:
2803:
3980:
2692:
297:
The assumption of the Karp–Lipton theorem, that these circuits exist, is weaker. But it is still possible for an algorithm in the complexity class
1992:
2551:
2264:
2442:
2168:
3645:
3452:
4083:
4156:
3710:
3591:
973:
165:), the theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems.
3211:
3006:
4229:
1316:
1167:
27:
3376:
3154:
3078:
729:
The Karp–Lipton theorem can be restated as a result about
Boolean formulas with polynomially-bounded quantifiers. Problems in
35:
3279:
1616:
3144:
762:
3922:
469:
is a correct circuit for solving SAT instances of a given size, and show that this circuit testing problem belongs to
2148:
1523:
361:
277:. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to
93:
1718:
870:
1975:
making the formula (1) false will work against any circuit. This property means a stronger collapse, namely to
718:
659:
To use self-reducibility to check the second property of a correct circuit for SAT, we rewrite it as follows:
3538:
3336:
2362:
1397:
52:
1070:
1775:
465:
To understand the Karp–Lipton proof in more detail, we consider the problem of testing whether a circuit
3906:{\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}}
3066:
1113:
150:
20:
4244:
2975:
1882:
1445:
840:
433:
331:
300:
210:
179:
142:
2137:{\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}\implies {\mathsf {AM}}={\mathsf {MA}}}
4262:
4224:
3914:
1947:
1912:
1835:
1286:
732:
686:
581:
472:
173:
4274:
4234:
4177:
1977:
278:
255:
2662:
2412:
1478:
1451:
1252:
1221:
946:
931:
is a valid circuit for SAT, then this subformula is equivalent to the unquantified formula
819:
412:
4258:
4220:
3835:
3531:
245:
239:
169:
158:
138:
39:
4152:
3057:, which is currently open and states that there exists a single language that is not in
4206:
4068:
2955:
2916:
1862:
204:
4181:
273:, or some other complexity classes are assumed to have polynomial-sized circuits; see
4289:
16:
On collapse of the polynomial hierarchy if NP is in non-uniform polynomial time class
4168:
Kannan, R. (1982). "Circuit-size lower bounds and non-reducibility to sparse sets".
4248:
3827:{\displaystyle {\mathsf {P^{\#P}}}\supseteq {\mathsf {PP}}\supseteq {\mathsf {MA}}}
3445:
A stronger version of Karp–Lipton theorem strengthens Kannan's theorem to: for any
2903:{\displaystyle z\notin L\implies \forall D.\Pr \nolimits _{x}\leq {\tfrac {1}{3}}}
675:) is true, the self-reduction procedure described above finds a valid solution to
141:, the class of nondeterministic polynomial time problems, can be contained in the
4210:
4140:
4045:{\displaystyle {\mathsf {PP}}=\Sigma _{2}\not \subseteq {\mathsf {SIZE}}(n^{k})}
2945:
154:
2792:{\displaystyle z\in L\implies \exists D.\Pr \nolimits _{x}\geq {\tfrac {2}{3}}}
4227:(1980), "Some connections between nonuniform and uniform complexity classes",
578:
The first of these two properties is already in the form of problems in class
43:
4195:
2044:{\displaystyle \Pi _{2}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}}
4239:
294:
constructible circuits for SAT would lead to a stronger collapse, P = NP.
161:. As P/poly contains all problems solvable in randomized polynomial time (
1608:
Furthermore, the circuit can be guessed with existential quantification:
4278:
2649:{\displaystyle z\notin L\implies \Pr \nolimits _{x}\leq {\tfrac {1}{3}}}
2349:{\displaystyle z\notin L\implies \Pr \nolimits _{x}\leq {\tfrac {1}{3}}}
3966:(follows from assumption using interactive protocol for permanent, see
282:
4230:
Proceedings of the
Twelfth Annual ACM Symposium on Theory of Computing
3967:
2540:{\displaystyle z\in L\implies \Pr \nolimits _{x}\geq {\tfrac {2}{3}}}
2253:{\displaystyle z\in L\implies \Pr \nolimits _{x}\geq {\tfrac {2}{3}}}
274:
270:
176:, who first proved it in 1980. (Their original proof collapsed PH to
162:
146:
3697:{\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})}
157:
problems. A proof that such circuits do not exist would imply that
3519:{\displaystyle L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})}
504:
is a correct circuit if and only if, for all polynomially-bounded
4133:{\displaystyle S_{2}^{P}\subseteq {\mathsf {ZPP}}^{\mathsf {NP}}}
3761:{\displaystyle {\mathsf {P^{\#P}}}\subseteq {\mathsf {P/poly}}}
3635:{\displaystyle {\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}}
496:. That is, there exists a polynomial time computable predicate
237:
Variants of the theorem state that, under the same assumption,
1048:{\displaystyle \exists c\forall (x,z)\;V(c,z)\wedge c(s(x))\,}
285:, then the polynomial hierarchy collapses to its third level.
3266:{\displaystyle {\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})}
1249:. Using self-reducibility, there exists a family of circuits
527:
is a correct circuit for SAT if it satisfies two properties:
269:
complexity class. There are stronger conclusions possible if
3050:{\displaystyle \Sigma _{2}\not \subseteq {\mathsf {P/poly}}}
19:
The notation used in this article is explained on the page
1384:{\displaystyle L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,}
1211:{\displaystyle {\mathsf {NP}}\subseteq {\mathsf {P/poly}}}
1276:
which outputs a satisfying assignment on true instances.
963:
is equivalent (under the assumption that a valid circuit
3434:{\displaystyle L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})}
3201:{\displaystyle {\mathsf {SAT}}\notin {\mathsf {P/poly}}}
3136:{\displaystyle L\in \Sigma _{4}-{\mathsf {SIZE}}(n^{k})}
756:
are described by formulas of this type, with the syntax
457:
can use it as a subroutine for solving other problems.
2941:
Application to circuit lower bounds – Kannan's theorem
2889:
2778:
2635:
2526:
2335:
2239:
4086:
3983:
3925:
3846:
3780:
3713:
3648:
3594:
3541:
3455:
3379:
3339:
3326:{\displaystyle {\mathsf {SAT}}\in {\mathsf {P/poly}}}
3282:
3214:
3157:
3081:
3009:
2978:
2958:
2919:
2806:
2695:
2665:
2554:
2445:
2415:
2365:
2267:
2171:
2068:
1995:
1950:
1915:
1885:
1865:
1838:
1778:
1721:
1680:{\displaystyle \exists D.\forall x.\phi (x,D(x,z),z)}
1619:
1526:
1481:
1454:
1400:
1319:
1289:
1255:
1224:
1170:
1116:
1073:
976:
949:
873:
843:
822:
765:
735:
689:
584:
475:
436:
415:
364:
334:
303:
213:
182:
96:
55:
806:{\displaystyle \phi =\forall x\exists y\;\psi (x,y)}
2436:that outputs a satisfying assignment if it exists:
149:, then this assumption implies the collapse of the
4132:
4044:
3959:{\displaystyle {\mathsf {P^{\#P}}}={\mathsf {MA}}}
3958:
3905:
3826:
3760:
3696:
3634:
3576:
3518:
3433:
3365:
3325:
3265:
3200:
3135:
3049:
2991:
2964:
2925:
2902:
2791:
2678:
2648:
2539:
2428:
2401:
2348:
2252:
2136:
2043:
1963:
1928:
1898:
1871:
1851:
1821:
1760:
1679:
1584:
1503:
1467:
1436:
1383:
1302:
1268:
1237:
1210:
1141:
1102:
1047:
955:
916:
856:
828:
805:
748:
702:
597:
488:
449:
421:
398:
347:
316:
226:
195:
126:
82:
4157:If NP has Polynomial-Size Circuits, then MA = AM
328:a correct circuit for SAT. The complexity class
1585:{\displaystyle \forall x.\phi (x,D_{n}(x,z),z)}
1218:. Therefore, there exists a family of circuits
1245:that solves satisfiability on input of length
399:{\displaystyle \exists x\forall y\;\psi (x,y)}
127:{\displaystyle {\mathsf {PH}}=\Sigma _{2}.\,}
8:
4265:(1982), "Turing machines that take advice",
3584:, which was proved by Vinodchandran. Proof:
1377:
1326:
605:. To verify the second property, we use the
4296:Theorems in computational complexity theory
4071:, Probabilistic quantifiers and games, 1988
3977:the containments are equalities and we get
1761:{\displaystyle \neg \exists y.\phi (x,y,z)}
2820:
2816:
2709:
2705:
2568:
2564:
2459:
2455:
2281:
2277:
2185:
2181:
2110:
2106:
1818:
1001:
917:{\displaystyle s(x)=\exists y\;\psi (x,y)}
895:
784:
377:
4238:
4120:
4119:
4107:
4106:
4096:
4091:
4085:
4033:
4011:
4010:
4001:
3985:
3984:
3982:
3947:
3946:
3932:
3927:
3926:
3924:
3894:
3893:
3884:
3868:
3867:
3853:
3848:
3847:
3845:
3815:
3814:
3802:
3801:
3787:
3782:
3781:
3779:
3739:
3735:
3734:
3720:
3715:
3714:
3712:
3685:
3663:
3662:
3650:
3649:
3647:
3613:
3609:
3608:
3596:
3595:
3593:
3565:
3543:
3542:
3540:
3507:
3485:
3484:
3475:
3470:
3464:
3463:
3454:
3422:
3400:
3399:
3390:
3378:
3357:
3344:
3338:
3304:
3300:
3299:
3284:
3283:
3281:
3254:
3232:
3231:
3216:
3215:
3213:
3179:
3175:
3174:
3159:
3158:
3156:
3124:
3102:
3101:
3092:
3080:
3028:
3024:
3023:
3014:
3008:
2983:
2977:
2957:
2918:
2888:
2834:
2805:
2777:
2723:
2694:
2670:
2664:
2634:
2598:
2573:
2553:
2525:
2489:
2464:
2444:
2420:
2414:
2364:
2334:
2286:
2266:
2238:
2190:
2170:
2125:
2124:
2112:
2111:
2087:
2083:
2082:
2070:
2069:
2067:
2059:A modification of the above proof yields
2035:
2022:
2017:
2011:
2010:
2000:
1994:
1955:
1949:
1920:
1914:
1890:
1884:
1864:
1843:
1837:
1777:
1720:
1618:
1552:
1525:
1496:
1488:
1480:
1459:
1453:
1444:can be considered an instance of SAT (by
1399:
1380:
1318:
1294:
1288:
1260:
1254:
1229:
1223:
1189:
1185:
1184:
1172:
1171:
1169:
1130:
1115:
1091:
1078:
1072:
1044:
975:
948:
872:
848:
842:
821:
764:
740:
734:
694:
688:
589:
583:
480:
474:
441:
435:
414:
363:
339:
333:
308:
302:
218:
212:
187:
181:
123:
114:
98:
97:
95:
79:
73:
60:
54:
3003:(n) (This is a different statement than
648:denotes the formula formed by replacing
4061:
3577:{\displaystyle {\mathsf {SIZE}}(n^{k})}
3366:{\displaystyle \Sigma _{4}=\Sigma _{2}}
168:The Karp–Lipton theorem is named after
4196:A note on the circuit complexity of PP
4124:
4121:
4114:
4111:
4108:
4021:
4018:
4015:
4012:
3989:
3986:
3951:
3948:
3936:
3933:
3929:
3898:
3895:
3872:
3869:
3857:
3854:
3850:
3819:
3816:
3806:
3803:
3791:
3788:
3784:
3753:
3750:
3747:
3744:
3740:
3736:
3724:
3721:
3717:
3673:
3670:
3667:
3664:
3654:
3651:
3627:
3624:
3621:
3618:
3614:
3610:
3600:
3597:
3553:
3550:
3547:
3544:
3495:
3492:
3489:
3486:
3465:
3410:
3407:
3404:
3401:
3318:
3315:
3312:
3309:
3305:
3301:
3291:
3288:
3285:
3242:
3239:
3236:
3233:
3223:
3220:
3217:
3193:
3190:
3187:
3184:
3180:
3176:
3166:
3163:
3160:
3112:
3109:
3106:
3103:
3042:
3039:
3036:
3033:
3029:
3025:
2402:{\displaystyle \exists y.\phi (x,y,z)}
2129:
2126:
2116:
2113:
2101:
2098:
2095:
2092:
2088:
2084:
2074:
2071:
2012:
1437:{\displaystyle \exists y.\phi (x,y,z)}
1203:
1200:
1197:
1194:
1190:
1186:
1176:
1173:
617:, choose one of the Boolean variables
102:
99:
83:{\displaystyle \Pi _{2}=\Sigma _{2}\,}
2948:'s theorem states that for any fixed
1103:{\displaystyle \Sigma _{2}=\Pi _{2}.}
281:. If coNP is assumed to be subset of
7:
4211:Oracles Are Subtle But Not Malicious
1610:
1517:
943:)). Therefore, the full formula for
714:is a valid circuit for solving SAT.
1822:{\displaystyle \phi (x,D(x,z),z)\;}
1062:is the formula used to verify that
927:is an instance of SAT. That is, if
3998:
3881:
3387:
3354:
3341:
3089:
3011:
2980:
2821:
2710:
2366:
2295:
2199:
2032:
1997:
1952:
1936:formula is true, then the circuit
1917:
1887:
1840:
1725:
1722:
1629:
1620:
1527:
1401:
1344:
1335:
1291:
1127:
1088:
1075:
983:
977:
889:
845:
778:
772:
737:
691:
586:
477:
438:
371:
365:
336:
305:
215:
184:
111:
70:
57:
14:
1511:, such that the formula defining
625:, and make two smaller instances
3147:technique). Consider two cases:
2051:). It was observed by Sengupta.
1772:can output an assignment making
3333:, then by Karp–Lipton theorem,
1142:{\displaystyle PH=\Sigma _{2}.}
547:is a solution to the instance,
355:describes problems of the form
4039:
4026:
3691:
3678:
3571:
3558:
3513:
3500:
3428:
3415:
3260:
3247:
3130:
3117:
2882:
2879:
2870:
2858:
2846:
2840:
2817:
2771:
2768:
2759:
2747:
2735:
2729:
2706:
2628:
2625:
2616:
2604:
2585:
2579:
2565:
2519:
2516:
2507:
2495:
2476:
2470:
2456:
2396:
2378:
2328:
2325:
2307:
2292:
2278:
2232:
2229:
2211:
2196:
2182:
2107:
1815:
1806:
1794:
1782:
1755:
1737:
1674:
1665:
1653:
1641:
1579:
1570:
1558:
1539:
1497:
1489:
1431:
1413:
1374:
1356:
1041:
1038:
1032:
1026:
1017:
1005:
998:
986:
911:
899:
883:
877:
800:
788:
393:
381:
36:Boolean satisfiability problem
1:
4182:10.1016/S0019-9958(82)90382-5
46:number of logic gates, then
725:Proof of Karp–Lipton theorem
4267:L'Enseignement Mathématique
2992:{\displaystyle \Sigma _{2}}
2831:
2720:
2570:
2461:
2283:
2187:
1899:{\displaystyle \Sigma _{2}}
1832:The proof has shown that a
1768:. In this case, no circuit
1711:
1705:
864:. Note that the subformula
857:{\displaystyle \Sigma _{2}}
450:{\displaystyle \Sigma _{2}}
348:{\displaystyle \Sigma _{2}}
317:{\displaystyle \Sigma _{2}}
227:{\displaystyle \Sigma _{2}}
196:{\displaystyle \Sigma _{3}}
143:non-uniform polynomial time
137:That is, if we assume that
4312:
3449:, there exists a language
2359:and as previously rewrite
1448:), there exists a circuit
543:is an instance of SAT and
18:
1715:). If (1) is false, then
3075:There exists a language
2952:there exists a language
2933:is in the smaller class
1964:{\displaystyle \Pi _{2}}
1929:{\displaystyle \Pi _{2}}
1852:{\displaystyle \Pi _{2}}
1303:{\displaystyle \Pi _{2}}
749:{\displaystyle \Pi _{2}}
719:Random self-reducibility
703:{\displaystyle \Pi _{1}}
598:{\displaystyle \Pi _{1}}
489:{\displaystyle \Pi _{1}}
4170:Information and Control
2940:
1989:complexity class (i.e.
1971:formula is false, then
967:exists) to the formula
430:the algorithm in class
38:(SAT) can be solved by
4151:V. Arvind, J. Köbler,
4134:
4046:
3960:
3907:
3828:
3762:
3698:
3636:
3578:
3529:It is also known that
3520:
3435:
3367:
3327:
3273:and theorem is proved.
3267:
3202:
3137:
3051:
2993:
2966:
2927:
2904:
2793:
2680:
2650:
2541:
2430:
2403:
2350:
2254:
2149:Arthur–Merlin protocol
2138:
2045:
1965:
1940:will work against any
1930:
1900:
1873:
1853:
1823:
1762:
1681:
1586:
1505:
1469:
1438:
1385:
1304:
1270:
1239:
1212:
1143:
1104:
1049:
957:
918:
858:
830:
807:
750:
721:for more information.
704:
599:
490:
451:
423:
400:
349:
318:
228:
197:
128:
84:
4240:10.1145/800141.804678
4194:N. V. Vinodchandran,
4135:
4047:
3961:
3908:
3829:
3763:
3699:
3637:
3579:
3521:
3436:
3368:
3328:
3268:
3203:
3138:
3052:
2994:
2967:
2928:
2905:
2794:
2681:
2679:{\displaystyle D_{n}}
2651:
2542:
2431:
2429:{\displaystyle D_{n}}
2404:
2351:
2255:
2139:
2046:
1966:
1931:
1901:
1874:
1854:
1824:
1763:
1682:
1587:
1506:
1504:{\displaystyle n=|z|}
1470:
1468:{\displaystyle D_{n}}
1439:
1386:
1305:
1271:
1269:{\displaystyle D_{n}}
1240:
1238:{\displaystyle C_{n}}
1213:
1144:
1105:
1050:
958:
956:{\displaystyle \phi }
919:
859:
831:
829:{\displaystyle \psi }
808:
751:
705:
683:Thus, we can test in
600:
491:
452:
424:
422:{\displaystyle \psi }
401:
350:
319:
229:
198:
129:
85:
4233:, pp. 302–309,
4084:
4052:by Kannan's theorem.
3981:
3923:
3844:
3778:
3711:
3646:
3592:
3539:
3535:is not contained in
3453:
3377:
3337:
3280:
3212:
3155:
3079:
3007:
2976:
2956:
2917:
2804:
2693:
2663:
2552:
2443:
2413:
2363:
2265:
2169:
2066:
1993:
1948:
1913:
1909:What's more, if the
1883:
1863:
1836:
1776:
1719:
1617:
1524:
1479:
1452:
1398:
1317:
1287:
1253:
1222:
1168:
1114:
1071:
974:
947:
871:
841:
820:
763:
733:
687:
582:
473:
434:
413:
362:
332:
301:
211:
180:
151:polynomial hierarchy
94:
53:
21:polynomial hierarchy
4279:10.5169/seals-52237
4101:
3917:and property of MA)
3480:
3067:circuit lower bound
2027:
1152:Another proof and S
663:For every instance
558:For every instance
34:states that if the
32:Karp–Lipton theorem
4130:
4087:
4042:
3956:
3903:
3824:
3758:
3694:
3632:
3574:
3516:
3462:
3431:
3363:
3323:
3263:
3198:
3133:
3065:). It is a simple
3047:
2999:, which is not in
2989:
2962:
2923:
2900:
2898:
2789:
2787:
2676:
2646:
2644:
2537:
2535:
2426:
2409:using the circuit
2399:
2346:
2344:
2250:
2248:
2134:
2041:
2009:
1961:
1926:
1896:
1869:
1849:
1819:
1758:
1677:
1582:
1501:
1465:
1446:Cook-Levin theorem
1434:
1381:
1300:
1266:
1235:
1208:
1139:
1100:
1045:
953:
914:
854:
826:
803:
746:
700:
652:with the constant
595:
486:
447:
419:
396:
345:
314:
224:
193:
124:
80:
2965:{\displaystyle L}
2926:{\displaystyle L}
2897:
2786:
2643:
2534:
2343:
2247:
1872:{\displaystyle L}
1701:
1700:
1606:
1605:
1515:is equivalent to
667:of SAT for which
621:that is input to
609:property of SAT.
607:self-reducibility
574:must be solvable.
562:of SAT for which
461:Self-reducibility
174:Richard J. Lipton
163:Adleman's theorem
145:complexity class
28:complexity theory
4303:
4281:
4251:
4242:
4213:
4204:
4198:
4192:
4186:
4185:
4165:
4159:
4149:
4143:
4139:
4137:
4136:
4131:
4129:
4128:
4127:
4118:
4117:
4100:
4095:
4078:
4072:
4066:
4051:
4049:
4048:
4043:
4038:
4037:
4025:
4024:
4006:
4005:
3993:
3992:
3965:
3963:
3962:
3957:
3955:
3954:
3942:
3941:
3940:
3939:
3912:
3910:
3909:
3904:
3902:
3901:
3889:
3888:
3876:
3875:
3863:
3862:
3861:
3860:
3834:(by property of
3833:
3831:
3830:
3825:
3823:
3822:
3810:
3809:
3797:
3796:
3795:
3794:
3767:
3765:
3764:
3759:
3757:
3756:
3743:
3730:
3729:
3728:
3727:
3703:
3701:
3700:
3695:
3690:
3689:
3677:
3676:
3658:
3657:
3641:
3639:
3638:
3633:
3631:
3630:
3617:
3604:
3603:
3583:
3581:
3580:
3575:
3570:
3569:
3557:
3556:
3525:
3523:
3522:
3517:
3512:
3511:
3499:
3498:
3479:
3474:
3469:
3468:
3440:
3438:
3437:
3432:
3427:
3426:
3414:
3413:
3395:
3394:
3372:
3370:
3369:
3364:
3362:
3361:
3349:
3348:
3332:
3330:
3329:
3324:
3322:
3321:
3308:
3295:
3294:
3272:
3270:
3269:
3264:
3259:
3258:
3246:
3245:
3227:
3226:
3207:
3205:
3204:
3199:
3197:
3196:
3183:
3170:
3169:
3143:(the proof uses
3142:
3140:
3139:
3134:
3129:
3128:
3116:
3115:
3097:
3096:
3056:
3054:
3053:
3048:
3046:
3045:
3032:
3019:
3018:
2998:
2996:
2995:
2990:
2988:
2987:
2971:
2969:
2968:
2963:
2932:
2930:
2929:
2924:
2909:
2907:
2906:
2901:
2899:
2890:
2839:
2838:
2798:
2796:
2795:
2790:
2788:
2779:
2728:
2727:
2686:can be guessed:
2685:
2683:
2682:
2677:
2675:
2674:
2655:
2653:
2652:
2647:
2645:
2636:
2603:
2602:
2578:
2577:
2546:
2544:
2543:
2538:
2536:
2527:
2494:
2493:
2469:
2468:
2435:
2433:
2432:
2427:
2425:
2424:
2408:
2406:
2405:
2400:
2355:
2353:
2352:
2347:
2345:
2336:
2291:
2290:
2259:
2257:
2256:
2251:
2249:
2240:
2195:
2194:
2143:
2141:
2140:
2135:
2133:
2132:
2120:
2119:
2105:
2104:
2091:
2078:
2077:
2050:
2048:
2047:
2042:
2040:
2039:
2026:
2021:
2016:
2015:
2005:
2004:
1986:
1985:
1970:
1968:
1967:
1962:
1960:
1959:
1935:
1933:
1932:
1927:
1925:
1924:
1905:
1903:
1902:
1897:
1895:
1894:
1878:
1876:
1875:
1870:
1858:
1856:
1855:
1850:
1848:
1847:
1828:
1826:
1825:
1820:
1767:
1765:
1764:
1759:
1695:
1686:
1684:
1683:
1678:
1611:
1600:
1591:
1589:
1588:
1583:
1557:
1556:
1518:
1510:
1508:
1507:
1502:
1500:
1492:
1474:
1472:
1471:
1466:
1464:
1463:
1443:
1441:
1440:
1435:
1390:
1388:
1387:
1382:
1309:
1307:
1306:
1301:
1299:
1298:
1275:
1273:
1272:
1267:
1265:
1264:
1244:
1242:
1241:
1236:
1234:
1233:
1217:
1215:
1214:
1209:
1207:
1206:
1193:
1180:
1179:
1160:
1159:
1148:
1146:
1145:
1140:
1135:
1134:
1109:
1107:
1106:
1101:
1096:
1095:
1083:
1082:
1054:
1052:
1051:
1046:
962:
960:
959:
954:
923:
921:
920:
915:
863:
861:
860:
855:
853:
852:
835:
833:
832:
827:
812:
810:
809:
804:
755:
753:
752:
747:
745:
744:
709:
707:
706:
701:
699:
698:
604:
602:
601:
596:
594:
593:
531:For every pair (
495:
493:
492:
487:
485:
484:
456:
454:
453:
448:
446:
445:
428:
426:
425:
420:
405:
403:
402:
397:
354:
352:
351:
346:
344:
343:
323:
321:
320:
315:
313:
312:
266:
265:
264:
233:
231:
230:
225:
223:
222:
202:
200:
199:
194:
192:
191:
133:
131:
130:
125:
119:
118:
106:
105:
89:
87:
86:
81:
78:
77:
65:
64:
40:Boolean circuits
4311:
4310:
4306:
4305:
4304:
4302:
4301:
4300:
4286:
4285:
4257:
4219:
4216:
4205:
4201:
4193:
4189:
4167:
4166:
4162:
4150:
4146:
4105:
4082:
4081:
4079:
4075:
4067:
4063:
4059:
4029:
3997:
3979:
3978:
3928:
3921:
3920:
3880:
3849:
3842:
3841:
3783:
3776:
3775:
3716:
3709:
3708:
3681:
3644:
3643:
3590:
3589:
3561:
3537:
3536:
3503:
3451:
3450:
3418:
3386:
3375:
3374:
3353:
3340:
3335:
3334:
3278:
3277:
3250:
3210:
3209:
3153:
3152:
3145:diagonalization
3120:
3088:
3077:
3076:
3072:Proof outline:
3010:
3005:
3004:
2979:
2974:
2973:
2954:
2953:
2943:
2915:
2914:
2830:
2802:
2801:
2719:
2691:
2690:
2666:
2661:
2660:
2594:
2569:
2550:
2549:
2485:
2460:
2441:
2440:
2416:
2411:
2410:
2361:
2360:
2282:
2263:
2262:
2186:
2167:
2166:
2064:
2063:
2057:
2031:
1996:
1991:
1990:
1984:
1981:
1980:
1979:
1951:
1946:
1945:
1916:
1911:
1910:
1886:
1881:
1880:
1861:
1860:
1839:
1834:
1833:
1774:
1773:
1717:
1716:
1693:
1615:
1614:
1598:
1548:
1522:
1521:
1477:
1476:
1475:, depending on
1455:
1450:
1449:
1396:
1395:
1315:
1314:
1290:
1285:
1284:
1256:
1251:
1250:
1225:
1220:
1219:
1166:
1165:
1162:
1158:
1155:
1154:
1153:
1126:
1112:
1111:
1087:
1074:
1069:
1068:
972:
971:
945:
944:
869:
868:
844:
839:
838:
818:
817:
761:
760:
736:
731:
730:
727:
690:
685:
684:
647:
638:
631:
585:
580:
579:
476:
471:
470:
463:
437:
432:
431:
411:
410:
360:
359:
335:
330:
329:
304:
299:
298:
291:
263:
260:
259:
258:
256:
214:
209:
208:
207:improved it to
183:
178:
177:
170:Richard M. Karp
110:
92:
91:
69:
56:
51:
50:
24:
17:
12:
11:
5:
4309:
4307:
4299:
4298:
4288:
4287:
4284:
4283:
4254:
4253:
4215:
4214:
4199:
4187:
4176:(1–3): 40–56.
4160:
4155:, R. Schuler,
4144:
4126:
4123:
4116:
4113:
4110:
4104:
4099:
4094:
4090:
4073:
4060:
4058:
4055:
4054:
4053:
4041:
4036:
4032:
4028:
4023:
4020:
4017:
4014:
4009:
4004:
4000:
3996:
3991:
3988:
3974:
3973:
3972:
3971:
3953:
3950:
3945:
3938:
3935:
3931:
3918:
3915:Toda's theorem
3900:
3897:
3892:
3887:
3883:
3879:
3874:
3871:
3866:
3859:
3856:
3852:
3839:
3821:
3818:
3813:
3808:
3805:
3800:
3793:
3790:
3786:
3770:
3769:
3755:
3752:
3749:
3746:
3742:
3738:
3733:
3726:
3723:
3719:
3705:
3693:
3688:
3684:
3680:
3675:
3672:
3669:
3666:
3661:
3656:
3653:
3629:
3626:
3623:
3620:
3616:
3612:
3607:
3602:
3599:
3573:
3568:
3564:
3560:
3555:
3552:
3549:
3546:
3515:
3510:
3506:
3502:
3497:
3494:
3491:
3488:
3483:
3478:
3473:
3467:
3461:
3458:
3443:
3442:
3430:
3425:
3421:
3417:
3412:
3409:
3406:
3403:
3398:
3393:
3389:
3385:
3382:
3373:and therefore
3360:
3356:
3352:
3347:
3343:
3320:
3317:
3314:
3311:
3307:
3303:
3298:
3293:
3290:
3287:
3274:
3262:
3257:
3253:
3249:
3244:
3241:
3238:
3235:
3230:
3225:
3222:
3219:
3195:
3192:
3189:
3186:
3182:
3178:
3173:
3168:
3165:
3162:
3132:
3127:
3123:
3119:
3114:
3111:
3108:
3105:
3100:
3095:
3091:
3087:
3084:
3044:
3041:
3038:
3035:
3031:
3027:
3022:
3017:
3013:
2986:
2982:
2961:
2942:
2939:
2922:
2911:
2910:
2896:
2893:
2887:
2884:
2881:
2878:
2875:
2872:
2869:
2866:
2863:
2860:
2857:
2854:
2851:
2848:
2845:
2842:
2837:
2833:
2829:
2826:
2823:
2819:
2815:
2812:
2809:
2799:
2785:
2782:
2776:
2773:
2770:
2767:
2764:
2761:
2758:
2755:
2752:
2749:
2746:
2743:
2740:
2737:
2734:
2731:
2726:
2722:
2718:
2715:
2712:
2708:
2704:
2701:
2698:
2673:
2669:
2657:
2656:
2642:
2639:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2601:
2597:
2593:
2590:
2587:
2584:
2581:
2576:
2572:
2567:
2563:
2560:
2557:
2547:
2533:
2530:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2497:
2492:
2488:
2484:
2481:
2478:
2475:
2472:
2467:
2463:
2458:
2454:
2451:
2448:
2423:
2419:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2357:
2356:
2342:
2339:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2289:
2285:
2280:
2276:
2273:
2270:
2260:
2246:
2243:
2237:
2234:
2231:
2228:
2225:
2222:
2219:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2193:
2189:
2184:
2180:
2177:
2174:
2145:
2144:
2131:
2128:
2123:
2118:
2115:
2109:
2103:
2100:
2097:
2094:
2090:
2086:
2081:
2076:
2073:
2056:
2053:
2038:
2034:
2030:
2025:
2020:
2014:
2008:
2003:
1999:
1982:
1958:
1954:
1923:
1919:
1893:
1889:
1868:
1846:
1842:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1699:
1698:
1689:
1687:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1604:
1603:
1594:
1592:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1560:
1555:
1551:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1499:
1495:
1491:
1487:
1484:
1462:
1458:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1392:
1391:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1297:
1293:
1263:
1259:
1232:
1228:
1205:
1202:
1199:
1196:
1192:
1188:
1183:
1178:
1175:
1161:
1156:
1150:
1138:
1133:
1129:
1125:
1122:
1119:
1099:
1094:
1090:
1086:
1081:
1077:
1056:
1055:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1000:
997:
994:
991:
988:
985:
982:
979:
952:
925:
924:
913:
910:
907:
904:
901:
898:
894:
891:
888:
885:
882:
879:
876:
851:
847:
825:
814:
813:
802:
799:
796:
793:
790:
787:
783:
780:
777:
774:
771:
768:
743:
739:
726:
723:
697:
693:
681:
680:
643:
636:
629:
592:
588:
576:
575:
556:
555:) must be true
483:
479:
462:
459:
444:
440:
418:
407:
406:
395:
392:
389:
386:
383:
380:
376:
373:
370:
367:
342:
338:
311:
307:
290:
287:
261:
221:
217:
205:Michael Sipser
190:
186:
135:
134:
122:
117:
113:
109:
104:
101:
90:and therefore
76:
72:
68:
63:
59:
15:
13:
10:
9:
6:
4:
3:
2:
4308:
4297:
4294:
4293:
4291:
4280:
4276:
4272:
4268:
4264:
4263:Lipton, R. J.
4260:
4256:
4255:
4250:
4246:
4241:
4236:
4232:
4231:
4226:
4225:Lipton, R. J.
4222:
4218:
4217:
4212:
4208:
4203:
4200:
4197:
4191:
4188:
4183:
4179:
4175:
4171:
4164:
4161:
4158:
4154:
4148:
4145:
4141:
4102:
4097:
4092:
4088:
4077:
4074:
4070:
4065:
4062:
4056:
4034:
4030:
4007:
4002:
3994:
3976:
3975:
3969:
3943:
3919:
3916:
3890:
3885:
3877:
3864:
3840:
3837:
3811:
3798:
3774:
3773:
3772:
3771:
3731:
3706:
3686:
3682:
3659:
3605:
3587:
3586:
3585:
3566:
3562:
3534:
3533:
3527:
3508:
3504:
3481:
3476:
3471:
3459:
3456:
3448:
3423:
3419:
3396:
3391:
3383:
3380:
3358:
3350:
3345:
3296:
3275:
3255:
3251:
3228:
3171:
3150:
3149:
3148:
3146:
3125:
3121:
3098:
3093:
3085:
3082:
3073:
3070:
3068:
3064:
3060:
3020:
3015:
3002:
2984:
2959:
2951:
2947:
2938:
2936:
2920:
2913:which proves
2894:
2891:
2885:
2876:
2873:
2867:
2864:
2861:
2855:
2852:
2849:
2843:
2835:
2827:
2824:
2813:
2810:
2807:
2800:
2783:
2780:
2774:
2765:
2762:
2756:
2753:
2750:
2744:
2741:
2738:
2732:
2724:
2716:
2713:
2702:
2699:
2696:
2689:
2688:
2687:
2671:
2667:
2640:
2637:
2631:
2622:
2619:
2613:
2610:
2607:
2599:
2595:
2591:
2588:
2582:
2574:
2561:
2558:
2555:
2548:
2531:
2528:
2522:
2513:
2510:
2504:
2501:
2498:
2490:
2486:
2482:
2479:
2473:
2465:
2452:
2449:
2446:
2439:
2438:
2437:
2421:
2417:
2393:
2390:
2387:
2384:
2381:
2375:
2372:
2369:
2340:
2337:
2331:
2322:
2319:
2316:
2313:
2310:
2304:
2301:
2298:
2287:
2274:
2271:
2268:
2261:
2244:
2241:
2235:
2226:
2223:
2220:
2217:
2214:
2208:
2205:
2202:
2191:
2178:
2175:
2172:
2165:
2164:
2163:
2161:
2157:
2154:Suppose that
2152:
2150:
2121:
2079:
2062:
2061:
2060:
2054:
2052:
2036:
2028:
2023:
2018:
2006:
2001:
1988:
1987:
1974:
1956:
1943:
1939:
1921:
1907:
1891:
1866:
1844:
1830:
1812:
1809:
1803:
1800:
1797:
1791:
1788:
1785:
1779:
1771:
1752:
1749:
1746:
1743:
1740:
1734:
1731:
1728:
1714:
1713:
1708:
1707:
1697:
1690:
1688:
1671:
1668:
1662:
1659:
1656:
1650:
1647:
1644:
1638:
1635:
1632:
1626:
1623:
1613:
1612:
1609:
1602:
1595:
1593:
1576:
1573:
1567:
1564:
1561:
1553:
1549:
1545:
1542:
1536:
1533:
1530:
1520:
1519:
1516:
1514:
1493:
1485:
1482:
1460:
1456:
1447:
1428:
1425:
1422:
1419:
1416:
1410:
1407:
1404:
1371:
1368:
1365:
1362:
1359:
1353:
1350:
1347:
1341:
1338:
1332:
1329:
1323:
1320:
1313:
1312:
1311:
1295:
1282:
1277:
1261:
1257:
1248:
1230:
1226:
1181:
1151:
1149:
1136:
1131:
1123:
1120:
1117:
1097:
1092:
1084:
1079:
1065:
1061:
1035:
1029:
1023:
1020:
1014:
1011:
1008:
1002:
995:
992:
989:
980:
970:
969:
968:
966:
950:
942:
938:
934:
930:
908:
905:
902:
896:
892:
886:
880:
874:
867:
866:
865:
849:
823:
797:
794:
791:
785:
781:
775:
769:
766:
759:
758:
757:
741:
724:
722:
720:
715:
713:
695:
678:
674:
670:
666:
662:
661:
660:
657:
655:
651:
646:
642:
635:
628:
624:
620:
616:
610:
608:
590:
573:
569:
565:
561:
557:
554:
550:
546:
542:
538:
534:
530:
529:
528:
526:
521:
519:
515:
511:
507:
503:
499:
481:
468:
460:
458:
442:
416:
390:
387:
384:
378:
374:
368:
358:
357:
356:
340:
327:
309:
295:
288:
286:
284:
280:
276:
272:
268:
267:
253:collapses to
252:
248:
247:
242:
241:
235:
219:
206:
188:
175:
171:
166:
164:
160:
156:
152:
148:
144:
140:
120:
115:
107:
74:
66:
61:
49:
48:
47:
45:
41:
37:
33:
29:
22:
4270:
4266:
4228:
4202:
4190:
4173:
4169:
4163:
4147:
4080:Jin Yi-Cai.
4076:
4064:
3530:
3528:
3446:
3444:
3074:
3071:
3062:
3061:(n) for any
3058:
3000:
2949:
2944:
2934:
2912:
2658:
2358:
2159:
2155:
2153:
2146:
2058:
1976:
1972:
1941:
1937:
1908:
1831:
1769:
1710:
1704:
1702:
1691:
1607:
1596:
1512:
1393:
1280:
1278:
1246:
1163:
1063:
1059:
1057:
964:
940:
936:
932:
928:
926:
815:
728:
716:
711:
682:
676:
672:
668:
664:
658:
653:
649:
644:
640:
633:
626:
622:
618:
614:
611:
606:
577:
571:
567:
563:
559:
552:
548:
544:
540:
536:
532:
524:
523:The circuit
522:
517:
513:
509:
505:
501:
497:
466:
464:
408:
325:
296:
292:
254:
250:
244:
238:
236:
167:
136:
31:
25:
4273:: 191–209,
4259:Karp, R. M.
4221:Karp, R. M.
4207:S. Aaronson
4153:U. Schöning
4142:, section 6
3707:Otherwise,
1709:) implies (
1703:Obviously (
570:) is true,
520:) is true.
155:NP-complete
4057:References
500:such that
44:polynomial
4103:⊆
4069:S. Zachos
3999:Σ
3934:#
3891:⊇
3882:Σ
3878:⊇
3865:⊇
3855:#
3812:⊇
3799:⊇
3789:#
3732:⊆
3722:#
3482:−
3460:∈
3397:−
3388:Σ
3384:∈
3355:Σ
3342:Σ
3297:∈
3229:∉
3172:∉
3099:−
3090:Σ
3086:∈
3012:Σ
2981:Σ
2886:≤
2844:ϕ
2822:∀
2818:⟹
2811:∉
2775:≥
2733:ϕ
2711:∃
2707:⟹
2700:∈
2632:≤
2583:ϕ
2566:⟹
2559:∉
2523:≥
2474:ϕ
2457:⟹
2450:∈
2376:ϕ
2367:∃
2332:≤
2305:ϕ
2296:∃
2279:⟹
2272:∉
2236:≥
2209:ϕ
2200:∃
2183:⟹
2176:∈
2108:⟹
2080:⊆
2033:Σ
2029:⊆
2007:⊆
1998:Π
1953:Π
1944:. If the
1918:Π
1888:Σ
1841:Π
1780:ϕ
1735:ϕ
1726:∃
1723:¬
1639:ϕ
1630:∀
1621:∃
1537:ϕ
1528:∀
1411:ϕ
1402:∃
1354:ϕ
1345:∃
1336:∀
1292:Π
1182:⊆
1128:Σ
1089:Π
1076:Σ
1021:∧
984:∀
978:∃
951:ϕ
897:ψ
890:∃
846:Σ
824:ψ
786:ψ
779:∃
773:∀
767:ϕ
738:Π
692:Π
587:Π
478:Π
439:Σ
417:ψ
379:ψ
372:∀
366:∃
337:Σ
306:Σ
289:Intuition
216:Σ
185:Σ
112:Σ
71:Σ
58:Π
4290:Category
4008:⊈
3660:⊈
3606:⊈
3021:⊈
2162:, i.e.:
1279:Suppose
710:whether
539:) where
4249:1458043
3768:. Since
2055:AM = MA
1164:Assume
283:NP/poly
42:with a
4247:
3968:P/poly
2946:Kannan
2659:Since
2158:is in
1879:is in
1829:true.
1394:Since
1058:where
816:where
639:where
409:where
275:P/poly
271:PSPACE
249:, and
203:, but
159:P ≠ NP
147:P/poly
30:, the
4245:S2CID
3642:then
3208:then
2147:(see
1283:is a
326:guess
3913:(by
3059:SIZE
3001:SIZE
1859:set
1310:set
717:See
632:and
172:and
4275:doi
4235:doi
4178:doi
3588:If
3276:If
3151:If
2972:in
2151:).
324:to
279:BPP
234:.)
26:In
4292::
4271:28
4269:,
4261:;
4243:,
4223:;
4209:,
4174:55
4172:.
3836:MA
3532:PP
3526:.
3069:.
2937:.
2935:MA
2832:Pr
2721:Pr
2571:Pr
2462:Pr
2284:Pr
2188:Pr
2160:AM
1906:.
508:,
251:PH
246:AM
243:=
240:MA
139:NP
4282:.
4277::
4252:.
4237::
4184:.
4180::
4125:P
4122:N
4115:P
4112:P
4109:Z
4098:P
4093:2
4089:S
4040:)
4035:k
4031:n
4027:(
4022:E
4019:Z
4016:I
4013:S
4003:2
3995:=
3990:P
3987:P
3970:)
3952:A
3949:M
3944:=
3937:P
3930:P
3899:A
3896:M
3886:2
3873:H
3870:P
3858:P
3851:P
3838:)
3820:A
3817:M
3807:P
3804:P
3792:P
3785:P
3754:y
3751:l
3748:o
3745:p
3741:/
3737:P
3725:P
3718:P
3704:.
3692:)
3687:k
3683:n
3679:(
3674:E
3671:Z
3668:I
3665:S
3655:P
3652:P
3628:y
3625:l
3622:o
3619:p
3615:/
3611:P
3601:P
3598:P
3572:)
3567:k
3563:n
3559:(
3554:E
3551:Z
3548:I
3545:S
3514:)
3509:k
3505:n
3501:(
3496:E
3493:Z
3490:I
3487:S
3477:P
3472:2
3466:S
3457:L
3447:k
3441:.
3429:)
3424:k
3420:n
3416:(
3411:E
3408:Z
3405:I
3402:S
3392:2
3381:L
3359:2
3351:=
3346:4
3319:y
3316:l
3313:o
3310:p
3306:/
3302:P
3292:T
3289:A
3286:S
3261:)
3256:k
3252:n
3248:(
3243:E
3240:Z
3237:I
3234:S
3224:T
3221:A
3218:S
3194:y
3191:l
3188:o
3185:p
3181:/
3177:P
3167:T
3164:A
3161:S
3131:)
3126:k
3122:n
3118:(
3113:E
3110:Z
3107:I
3104:S
3094:4
3083:L
3063:k
3043:y
3040:l
3037:o
3034:p
3030:/
3026:P
3016:2
2985:2
2960:L
2950:k
2921:L
2895:3
2892:1
2883:]
2880:)
2877:z
2874:,
2871:)
2868:z
2865:,
2862:x
2859:(
2856:D
2853:,
2850:x
2847:(
2841:[
2836:x
2828:.
2825:D
2814:L
2808:z
2784:3
2781:2
2772:]
2769:)
2766:z
2763:,
2760:)
2757:z
2754:,
2751:x
2748:(
2745:D
2742:,
2739:x
2736:(
2730:[
2725:x
2717:.
2714:D
2703:L
2697:z
2672:n
2668:D
2641:3
2638:1
2629:]
2626:)
2623:z
2620:,
2617:)
2614:z
2611:,
2608:x
2605:(
2600:n
2596:D
2592:,
2589:x
2586:(
2580:[
2575:x
2562:L
2556:z
2532:3
2529:2
2520:]
2517:)
2514:z
2511:,
2508:)
2505:z
2502:,
2499:x
2496:(
2491:n
2487:D
2483:,
2480:x
2477:(
2471:[
2466:x
2453:L
2447:z
2422:n
2418:D
2397:)
2394:z
2391:,
2388:y
2385:,
2382:x
2379:(
2373:.
2370:y
2341:3
2338:1
2329:]
2326:)
2323:z
2320:,
2317:y
2314:,
2311:x
2308:(
2302:.
2299:y
2293:[
2288:x
2275:L
2269:z
2245:3
2242:2
2233:]
2230:)
2227:z
2224:,
2221:y
2218:,
2215:x
2212:(
2206:.
2203:y
2197:[
2192:x
2179:L
2173:z
2156:L
2130:A
2127:M
2122:=
2117:M
2114:A
2102:y
2099:l
2096:o
2093:p
2089:/
2085:P
2075:P
2072:N
2037:2
2024:P
2019:2
2013:S
2002:2
1983:2
1978:S
1973:x
1957:2
1942:x
1938:D
1922:2
1892:2
1867:L
1845:2
1816:)
1813:z
1810:,
1807:)
1804:z
1801:,
1798:x
1795:(
1792:D
1789:,
1786:x
1783:(
1770:D
1756:)
1753:z
1750:,
1747:y
1744:,
1741:x
1738:(
1732:.
1729:y
1712:2
1706:1
1696:)
1694:2
1692:(
1675:)
1672:z
1669:,
1666:)
1663:z
1660:,
1657:x
1654:(
1651:D
1648:,
1645:x
1642:(
1636:.
1633:x
1627:.
1624:D
1601:)
1599:1
1597:(
1580:)
1577:z
1574:,
1571:)
1568:z
1565:,
1562:x
1559:(
1554:n
1550:D
1546:,
1543:x
1540:(
1534:.
1531:x
1513:L
1498:|
1494:z
1490:|
1486:=
1483:n
1461:n
1457:D
1432:)
1429:z
1426:,
1423:y
1420:,
1417:x
1414:(
1408:.
1405:y
1378:}
1375:)
1372:z
1369:,
1366:y
1363:,
1360:x
1357:(
1351:.
1348:y
1342:.
1339:x
1333::
1330:z
1327:{
1324:=
1321:L
1296:2
1281:L
1262:n
1258:D
1247:n
1231:n
1227:C
1204:y
1201:l
1198:o
1195:p
1191:/
1187:P
1177:P
1174:N
1157:2
1137:.
1132:2
1124:=
1121:H
1118:P
1098:.
1093:2
1085:=
1080:2
1064:c
1060:V
1042:)
1039:)
1036:x
1033:(
1030:s
1027:(
1024:c
1018:)
1015:z
1012:,
1009:c
1006:(
1003:V
999:)
996:z
993:,
990:x
987:(
981:c
965:c
941:x
939:(
937:s
935:(
933:c
929:c
912:)
909:y
906:,
903:x
900:(
893:y
887:=
884:)
881:x
878:(
875:s
850:2
801:)
798:y
795:,
792:x
789:(
782:y
776:x
770:=
742:2
712:c
696:1
679:.
677:s
673:s
671:(
669:c
665:s
654:i
650:x
645:i
641:s
637:1
634:s
630:0
627:s
623:s
619:x
615:s
591:1
572:s
568:s
566:(
564:c
560:s
553:s
551:(
549:c
545:x
541:s
537:x
535:,
533:s
525:c
518:z
516:,
514:c
512:(
510:V
506:z
502:c
498:V
482:1
467:c
443:2
394:)
391:y
388:,
385:x
382:(
375:y
369:x
341:2
310:2
262:2
257:S
220:2
189:3
121:.
116:2
108:=
103:H
100:P
75:2
67:=
62:2
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.