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