925:
1341:
780:
1450:
2083:
is also a 5-cycle. (The existence of such elements was established in Lemma 2.) If one or both of the circuits outputs 0, the resulting program will be the identity due to cancellation; if both circuits output 1, the resulting program will output the commutator
461:
1018:
820:
1219:
1238:
179:, but most researchers suspect this to be false, meaning that there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism. Just as the class
318:
An example of problem in NC is the parity check on a bit string. The problem consists in counting the number of 1s in a string made of 1 and 0. A simple solution consists in summing all the string's bits. Since
651:
689:
66:
1347:
1719:
Every regular language on {0,1} can be recognized by a family of branching programs of constant width and linear number of instructions (since a DFA can be converted to a branching program).
1755:
can be computed by a family of branching programs of constant width and polynomial size, while intuition might suggest that to achieve polynomial size, one needs a linear number of states.
1467:
operates only on a constant length of input bits. It is therefore described as the class of functions definable by uniform boolean circuits with constant depth and bounded fan-in.
326:
1100:
1647:
1614:
1680:
509:
563:
536:
940:
920:{\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {L}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq {\mathsf {P}}.}
72:
2713:
210:
is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor. It can be CRCW, CREW, or EREW. See
1716:
on {0,1} can be recognized by a family of branching programs of width 5 and exponential length, or by a family of exponential width and linear length.
1164:
1336:{\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}\subset \cdots \subset {\mathsf {NC}}^{i+j}\subset \cdots {\mathsf {NC}}}
206:). That is a parallel computer with a central pool of memory, and any processor can access any bit of memory in constant time. The definition of
1579:
of the program (more precisely, the yield on an input is the function mapping any initial state to the corresponding final state). The program
2485:
775:{\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots {\mathsf {NC}}}
664:
is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates of at most two inputs and depth
572:
3075:
2674:
2641:
2618:
2579:
2544:
2516:
27:
2706:
2175:
294:
Often algorithms for those problems had to be separately invented and could not be naïvely adapted from well-known algorithms –
1111:
79:
1445:{\displaystyle {\mathsf {NC}}^{1}\subset \cdots \subset {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}}
930:
The NC classes are related to the AC classes, which are defined similarly, but with gates having unbounded fan-in. For each
211:
203:
1763:
A branching program of constant width and polynomial size can be easily converted (via divide-and-conquer) to a circuit in
1455:
It is widely believed that (1) is the case, although no proof as to the truth of either statement has yet been discovered.
171:
because polylogarithmic parallel computations can be simulated by polynomial-time sequential ones. It is unknown whether
3115:
3110:
2699:
1723:
denotes the class of languages recognizable by a family of branching programs of bounded width and polynomial length.
2898:
225:(which can be calculated from the length of the input, for NC, we suppose we can compute the Boolean circuit of size
3091:
2477:
1043:
2317:
IAS/PCMI Summer
Session 2000 - Clay Mathematics Undergraduate Program - Basic Course on Computational Complexity
2157:
is the depth of the circuit. If the circuit has logarithmic depth, the branching program has polynomial length.
3080:
1539:
are called states of the branching program. The program initially starts in state 1, and each instruction (
3034:
2602:
456:{\displaystyle x_{1}+\cdots +x_{n}=(x_{1}+\cdots +x_{\frac {n}{2}})+(x_{{\frac {n}{2}}+1}+\cdots +x_{n})}
3029:
3024:
2243:
307:
274:
259:, by a slight abuse of language, one might classify function problems and search problems as being in
3019:
1734:
1057:
295:
91:
2533:
1619:
1586:
195:
reductions, can be thought of as "probably not parallelizable" or "probably inherently sequential".
2320:
1575:
th variable is 0 or 1. The function mapping an input to a final state of the program is called the
299:
2309:
2267:
303:
95:
1652:
156:
470:
3039:
2670:
2637:
2614:
2575:
2540:
2512:
2481:
2439:
2259:
2224:
1752:
146:, who had done extensive research on circuits with polylogarithmic depth and polynomial size.
2005:
and then multiply the output of the program by α. By Lemma 1, we get a branching program for
1013:{\displaystyle {\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {NC}}^{i+1}.}
3003:
2893:
2825:
2815:
2722:
2680:
2647:
2585:
2522:
2491:
2447:
2429:
2379:
2251:
2214:
566:
285:
87:
2928:
541:
514:
2998:
2988:
2945:
2935:
2918:
2908:
2866:
2861:
2856:
2840:
2820:
2798:
2793:
2776:
2771:
2766:
2761:
2684:
2666:
2651:
2589:
2571:
2526:
2508:
2495:
2451:
1844:
810:
804:
234:
222:
2410:
163:
can be thought of as the problems that can be efficiently solved on a parallel computer.
2993:
2881:
2803:
2756:
2630:
2411:"Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in
1741:
798:
278:
151:
143:
117:
2219:
2202:
2187:
3104:
2469:
2434:
1952:. We will show that for all 5-cycles α, there exists a branching program α-computing
2563:
2550:
2271:
683:)) on a parallel computer with a polynomial number of processors. Clearly, we have
139:
98:
with a polynomial number of processors. In other words, a problem with input size
2660:
2871:
2781:
1158:-hierarchy collapse because even a single equality in the chain of containments
464:
181:
1214:{\displaystyle {\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots }
2983:
2808:
2383:
2070:, and δ-compute B for a choice of 5-cycles γ and δ such that their commutator
1882:
187:
2443:
2263:
2228:
1774:
is given. Without loss of generality, assume it uses only AND and NOT gates.
2978:
15:
2370:
S. Bellantoni and I. Oitavem (2004). "Separating NC along the delta axis".
1784:
If there exists a branching program that sometimes works as a permutation
2973:
2968:
2913:
2736:
2255:
1843:
As a consequence of Lemma 1 and the fact that all cycles of length 5 are
320:
2963:
2110:
are two 5-cycles, they are conjugate, and hence there exists a program
2923:
3070:
3065:
2940:
2691:
2128:
By assuming the subcircuits have branching programs so that they are
2248:
20th Annual
Symposium on Foundations of Computer Science (SFCS 1979)
1751:
The theorem is rather surprising. For instance, it implies that the
1693:
A family of branching programs consists of a branching program with
1971:, the branching program we need has just one instruction: checking
646:{\displaystyle (x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})}
237:
depth and a polynomial number of gates with a maximum fan-in of 2.
3060:
3055:
2876:
2507:. Texts in Theoretical Computer Science. An EATCS Series. Berlin:
2209:. International Conference on Foundations of Computation Theory.
2176:"Towards a complexity theory of synchronous parallel computation"
2888:
2746:
1859:, then there exists a branching program β-computing the circuit
1792:, by right-multiplying permutations in the first instruction by
463:. Recursively applying such property, it is possible to build a
2695:
2636:. Progress in Theoretical Computer Science. Basel: Birkhäuser.
1118:
198:
The parallel computer in the definition can be assumed to be a
2903:
2835:
2830:
2751:
2741:
1948:
and 5-cycles α, there exists a branching program α-computing
302:
rely on operations performed in sequence. One might contrast
1855:, if there exists a branching program α-computing a circuit
61:{\displaystyle {\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}}
1800:, we can make a circuit of the same length that behaves as
1705:
variable program accepts the language restricted to length
185:
can be thought of as "probably intractable", so the class
221:
can be defined as those decision problems decidable by a
1616:
of variable values when there is some set of functions
284:
Polynomial GCD, by a reduction to linear algebra using
2662:
Introduction to circuit complexity. A uniform approach
2203:"A taxonomy of problems with fast parallel algorithms"
2153:
The size of the branching program is at most 4, where
2632:
Finite automata, formal logic, and circuit complexity
2536:
Limits To
Parallel computation; P-Completeness Theory
1917:
We will now prove
Barrington's theorem by induction:
1655:
1622:
1589:
1350:
1241:
1167:
1060:
943:
823:
692:
675:, or the class of decision problems solvable in time
575:
544:
517:
473:
329:
30:
1046:
restricted to at most two options at each step with
3048:
3012:
2956:
2849:
2729:
2534:Greenlaw, Raymond, James Hoover, and Walter Ruzzo.
1495:
instructions. Each of the instructions is a tuple (
2629:
2613:(1st ed.). Addison Wesley. pp. 375–381.
2308:David Mix Barrington; Alexis Maciel (2000-07-18).
1978:'s value (0 or 1), and outputting the identity or
1796:, and in the last instruction left-multiplying by
1674:
1641:
1608:
1444:
1335:
1213:
1094:
1031:. It is known that both inclusions are strict for
1023:As an immediate consequence of this, we have that
1012:
919:
774:
645:
557:
530:
503:
455:
60:
2665:. Texts in Theoretical Computer Science. Berlin:
1824:Call a branching program α-computing a circuit
271:Integer addition, multiplication and division;
2707:
1511:is the index of variable to check (1 ≤
1042:is equivalent to the problems solvable on an
267:is known to include many problems, including
155:can be thought of as the tractable problems (
8:
2310:"Lecture 2: The Complexity of Some Problems"
73:(more unsolved problems in computer science)
2474:Computational complexity. A modern approach
1867:
1778:
1114:is whether or not every containment in the
2714:
2700:
2692:
2503:Clote, Peter; Kranakis, Evangelos (2002).
2433:
2218:
1666:
1654:
1633:
1621:
1600:
1588:
1433:
1432:
1414:
1405:
1404:
1388:
1379:
1378:
1362:
1353:
1352:
1349:
1324:
1323:
1305:
1296:
1295:
1279:
1270:
1269:
1253:
1244:
1243:
1240:
1228:hierarchy "collapses" down to some level
1199:
1190:
1189:
1179:
1170:
1169:
1166:
1077:
1059:
995:
986:
985:
975:
966:
965:
955:
946:
945:
942:
908:
907:
898:
889:
888:
878:
869:
868:
855:
854:
845:
844:
835:
826:
825:
822:
763:
762:
750:
741:
740:
724:
715:
714:
704:
695:
694:
691:
634:
621:
599:
583:
574:
549:
543:
522:
516:
472:
444:
413:
412:
388:
369:
353:
334:
328:
52:
51:
41:
32:
31:
29:
2505:Boolean functions and computation models
2395:
2393:
2347:
2345:
2294:
2292:
2290:
2166:
1712:It is easy to show that every language
1437:
1434:
1409:
1406:
1383:
1380:
1357:
1354:
1328:
1325:
1300:
1297:
1274:
1271:
1248:
1245:
1194:
1191:
1174:
1171:
990:
987:
970:
967:
950:
947:
909:
893:
890:
873:
870:
859:
856:
846:
830:
827:
767:
764:
745:
742:
719:
716:
699:
696:
569:, e.g. through the boolean expression
53:
36:
33:
2555:The design and analysis of algorithms
2149:also has this property, as required.
142:coined the name "Nick's class" after
7:
1940:and assume that for all subcircuits
511:in which every sum between two bits
18:Unsolved problem in computer science
2088:. In other words, we get a program
2046:, join the branching programs that
2009:outputting the identity or α, i.e.
1232:. Thus, there are 2 possibilities:
114:such that it can be solved in time
86:(for "Nick's Class") is the set of
614:
592:
214:for descriptions of those models.
14:
3076:Probabilistically checkable proof
2605:(1993). "Section 15.3: The class
2351:Clote & Kranakis (2002) p.437
2339:Papadimitriou (1994) Theorem 16.1
2244:"On simultaneous resource bounds"
1770:Conversely, suppose a circuit in
1701:. It accepts a language when the
565:is expressible by means of basic
2399:Clote & Kranakis (2002) p.50
2360:Clote & Kranakis (2002) p.12
2201:Cook, Stephen A. (1985-01-01).
1788:and sometimes as a permutation
1686:precisely when its yield is in
1527:are functions from {1, 2, ...,
1154:. This observation is known as
1095:{\displaystyle (\log n)^{O(1)}}
200:parallel, random-access machine
80:computational complexity theory
2298:Arora & Barak (2009) p.118
2284:Arora & Barak (2009) p.120
1964:simply outputs some input bit
1649:such that a variable sequence
1642:{\displaystyle F\subset k^{k}}
1609:{\displaystyle A\subset 2^{n}}
1087:
1081:
1074:
1061:
640:
611:
605:
576:
498:
495:
489:
477:
450:
405:
399:
362:
1:
2570:. Texts in Computer Science.
2409:Barrington, David A. (1989).
2220:10.1016/S0019-9958(85)80041-3
1997:, create a branching program
1828:if it works as identity when
1759:Proof of Barrington's theorem
796:classes to the space classes
2435:10.1016/0022-0000(89)90037-8
2372:Theoretical Computer Science
2242:Pippenger, Nicholas (1979).
2132:-computing for all 5-cycles
1571:), depending on whether the
2180:L'Enseignement Mathématique
1993:for some different circuit
1897:is a 5-cycle. For example,
1110:One major open question in
1106:Open problem: Is NC proper?
290:Finding a maximal matching.
247:with access to randomness.
3132:
3092:List of complexity classes
2659:Vollmer, Heribert (1998).
2628:Straubing, Howard (1994).
2478:Cambridge University Press
1920:Suppose we have a circuit
1675:{\displaystyle x\in 2^{n}}
1491:consists of a sequence of
1044:alternating Turing machine
3089:
2384:10.1016/j.tcs.2003.10.021
1551:) changes the state from
504:{\displaystyle O(log(n))}
106:if there exist constants
3081:Interactive proof system
2611:Computational Complexity
2594:Lecture 12: Relation of
2186:: 99–124. Archived from
1744:of the symmetric group S
1224:implies that the entire
1038:Similarly, we have that
229:in logarithmic space in
2603:Papadimitriou, Christos
2559:Lectures 28 - 34 and 36
2207:Information and Control
1847:, for any two 5-cycles
1832:'s output is 0, and as
1758:
1470:
223:uniform Boolean circuit
3035:Arithmetical hierarchy
2472:; Barak, Boaz (2009).
1863:, of the same length.
1676:
1643:
1610:
1535:}. Numbers 1, 2, ...,
1446:
1337:
1215:
1096:
1014:
921:
776:
647:
559:
532:
505:
457:
62:
3030:Grzegorczyk hierarchy
3025:Exponential hierarchy
2957:Considered infeasible
2598:to Time-Space Classes
2568:Theory of Computation
1905:= (1 3 5 4 2) giving
1873:There exist 5-cycles
1740:. The proof uses the
1677:
1644:
1611:
1447:
1338:
1216:
1097:
1015:
922:
777:
648:
560:
558:{\displaystyle x_{j}}
533:
531:{\displaystyle x_{i}}
506:
458:
308:carry-lookahead adder
275:Matrix multiplication
243:is a class extending
138:parallel processors.
63:
3020:Polynomial hierarchy
2850:Suspected infeasible
2422:J. Comput. Syst. Sci
2256:10.1109/SFCS.1979.29
1727:Barrington's theorem
1653:
1620:
1587:
1471:Barrington's theorem
1348:
1239:
1165:
1058:
941:
821:
690:
573:
542:
515:
471:
327:
296:Gaussian elimination
92:polylogarithmic time
28:
3049:Families of classes
2730:Considered feasible
2321:Clarkson University
2174:Cook, S.A. (1981).
1924:which takes inputs
1871: —
1782: —
1697:variables for each
1483:variables of width
1146:, and as a result,
300:Euclidean algorithm
3116:Circuit complexity
3111:Complexity classes
2723:Complexity classes
1915:
1869:
1780:
1672:
1639:
1606:
1463:The special class
1442:
1333:
1211:
1092:
1010:
917:
792:We can relate the
772:
643:
555:
528:
501:
453:
304:ripple carry adder
149:Just as the class
58:
3098:
3097:
3040:Boolean hierarchy
3013:Class hierarchies
2487:978-0-521-42426-4
1913:
1753:majority function
1531:} to {1, 2, ...,
1477:branching program
1112:complexity theory
567:logical operators
421:
396:
96:parallel computer
88:decision problems
49:
3123:
2716:
2709:
2702:
2693:
2688:
2655:
2635:
2624:
2593:
2564:Kozen, Dexter C.
2558:
2551:Kozen, Dexter C.
2530:
2499:
2456:
2455:
2437:
2419:
2406:
2400:
2397:
2388:
2387:
2367:
2361:
2358:
2352:
2349:
2340:
2337:
2331:
2330:
2328:
2327:
2314:
2305:
2299:
2296:
2285:
2282:
2276:
2275:
2239:
2233:
2232:
2222:
2198:
2192:
2191:
2171:
2145:, we have shown
2144:
2123:
2101:
2082:
2037:
1896:
1881:such that their
1872:
1840:'s output is 1.
1820:, respectively.
1783:
1681:
1679:
1678:
1673:
1671:
1670:
1648:
1646:
1645:
1640:
1638:
1637:
1615:
1613:
1612:
1607:
1605:
1604:
1451:
1449:
1448:
1443:
1441:
1440:
1425:
1424:
1413:
1412:
1393:
1392:
1387:
1386:
1367:
1366:
1361:
1360:
1342:
1340:
1339:
1334:
1332:
1331:
1316:
1315:
1304:
1303:
1284:
1283:
1278:
1277:
1258:
1257:
1252:
1251:
1220:
1218:
1217:
1212:
1204:
1203:
1198:
1197:
1184:
1183:
1178:
1177:
1101:
1099:
1098:
1093:
1091:
1090:
1019:
1017:
1016:
1011:
1006:
1005:
994:
993:
980:
979:
974:
973:
960:
959:
954:
953:
926:
924:
923:
918:
913:
912:
903:
902:
897:
896:
883:
882:
877:
876:
863:
862:
850:
849:
840:
839:
834:
833:
785:which forms the
781:
779:
778:
773:
771:
770:
755:
754:
749:
748:
729:
728:
723:
722:
709:
708:
703:
702:
674:
657:The NC hierarchy
652:
650:
649:
644:
639:
638:
626:
625:
604:
603:
588:
587:
564:
562:
561:
556:
554:
553:
537:
535:
534:
529:
527:
526:
510:
508:
507:
502:
462:
460:
459:
454:
449:
448:
430:
429:
422:
414:
398:
397:
389:
374:
373:
358:
357:
339:
338:
323:is associative,
286:Sylvester matrix
137:
126:
69:
67:
65:
64:
59:
57:
56:
50:
42:
40:
39:
19:
3131:
3130:
3126:
3125:
3124:
3122:
3121:
3120:
3101:
3100:
3099:
3094:
3085:
3044:
3008:
2952:
2946:PSPACE-complete
2845:
2725:
2720:
2677:
2667:Springer-Verlag
2658:
2644:
2627:
2621:
2601:
2582:
2572:Springer-Verlag
2562:
2549:
2519:
2509:Springer-Verlag
2502:
2488:
2468:
2465:
2460:
2459:
2417:
2408:
2407:
2403:
2398:
2391:
2369:
2368:
2364:
2359:
2355:
2350:
2343:
2338:
2334:
2325:
2323:
2312:
2307:
2306:
2302:
2297:
2288:
2283:
2279:
2241:
2240:
2236:
2200:
2199:
2195:
2173:
2172:
2168:
2163:
2151:
2143:
2136:
2133:
2131:
2115:
2113:
2109:
2105:
2093:
2091:
2087:
2071:
2065:
2057:
2049:
2029:
2024:If the circuit
2012:
2000:
1985:If the circuit
1982:(respectively).
1981:
1977:
1976:
1969:
1960:If the circuit
1939:
1930:
1911:
1909:= (1 3 2 5 4).
1908:
1904:
1901:= (1 2 3 4 5),
1900:
1885:
1880:
1876:
1870:
1854:
1850:
1839:
1835:
1831:
1822:
1819:
1813:
1809:
1803:
1799:
1795:
1781:
1761:
1747:
1662:
1651:
1650:
1629:
1618:
1617:
1596:
1585:
1584:
1473:
1461:
1403:
1377:
1351:
1346:
1345:
1294:
1268:
1242:
1237:
1236:
1188:
1168:
1163:
1162:
1108:
1073:
1056:
1055:
984:
964:
944:
939:
938:
887:
867:
824:
819:
818:
739:
713:
693:
688:
687:
665:
659:
630:
617:
595:
579:
571:
570:
545:
540:
539:
518:
513:
512:
469:
468:
440:
408:
384:
365:
349:
330:
325:
324:
316:
277:, determinant,
253:
235:polylogarithmic
167:is a subset of
157:Cobham's thesis
128:
115:
76:
75:
70:
26:
25:
23:
21:
17:
12:
11:
5:
3129:
3127:
3119:
3118:
3113:
3103:
3102:
3096:
3095:
3090:
3087:
3086:
3084:
3083:
3078:
3073:
3068:
3063:
3058:
3052:
3050:
3046:
3045:
3043:
3042:
3037:
3032:
3027:
3022:
3016:
3014:
3010:
3009:
3007:
3006:
3001:
2996:
2991:
2986:
2981:
2976:
2971:
2966:
2960:
2958:
2954:
2953:
2951:
2950:
2949:
2948:
2938:
2933:
2932:
2931:
2921:
2916:
2911:
2906:
2901:
2896:
2891:
2886:
2885:
2884:
2882:co-NP-complete
2879:
2874:
2869:
2859:
2853:
2851:
2847:
2846:
2844:
2843:
2838:
2833:
2828:
2823:
2818:
2813:
2812:
2811:
2801:
2796:
2791:
2786:
2785:
2784:
2774:
2769:
2764:
2759:
2754:
2749:
2744:
2739:
2733:
2731:
2727:
2726:
2721:
2719:
2718:
2711:
2704:
2696:
2690:
2689:
2675:
2656:
2642:
2625:
2619:
2599:
2580:
2560:
2547:
2531:
2517:
2500:
2486:
2470:Arora, Sanjeev
2464:
2461:
2458:
2457:
2428:(1): 150–164.
2401:
2389:
2378:(1–2): 57–78.
2362:
2353:
2341:
2332:
2300:
2286:
2277:
2234:
2193:
2190:on 2022-03-10.
2165:
2164:
2162:
2159:
2141:
2134:
2129:
2126:
2125:
2111:
2107:
2103:
2089:
2085:
2063:
2055:
2047:
2022:
2010:
1998:
1983:
1979:
1974:
1972:
1967:
1935:
1928:
1912:
1906:
1902:
1898:
1878:
1874:
1865:
1852:
1848:
1837:
1833:
1829:
1817:
1811:
1807:
1801:
1797:
1793:
1776:
1760:
1757:
1745:
1742:nonsolvability
1669:
1665:
1661:
1658:
1636:
1632:
1628:
1625:
1603:
1599:
1595:
1592:
1472:
1469:
1460:
1457:
1453:
1452:
1439:
1436:
1431:
1428:
1423:
1420:
1417:
1411:
1408:
1402:
1399:
1396:
1391:
1385:
1382:
1376:
1373:
1370:
1365:
1359:
1356:
1343:
1330:
1327:
1322:
1319:
1314:
1311:
1308:
1302:
1299:
1293:
1290:
1287:
1282:
1276:
1273:
1267:
1264:
1261:
1256:
1250:
1247:
1222:
1221:
1210:
1207:
1202:
1196:
1193:
1187:
1182:
1176:
1173:
1107:
1104:
1102:alternations.
1089:
1086:
1083:
1080:
1076:
1072:
1069:
1066:
1063:
1021:
1020:
1009:
1004:
1001:
998:
992:
989:
983:
978:
972:
969:
963:
958:
952:
949:
928:
927:
916:
911:
906:
901:
895:
892:
886:
881:
875:
872:
866:
861:
858:
853:
848:
843:
838:
832:
829:
783:
782:
769:
766:
761:
758:
753:
747:
744:
738:
735:
732:
727:
721:
718:
712:
707:
701:
698:
658:
655:
642:
637:
633:
629:
624:
620:
616:
613:
610:
607:
602:
598:
594:
591:
586:
582:
578:
552:
548:
525:
521:
500:
497:
494:
491:
488:
485:
482:
479:
476:
452:
447:
443:
439:
436:
433:
428:
425:
420:
417:
411:
407:
404:
401:
395:
392:
387:
383:
380:
377:
372:
368:
364:
361:
356:
352:
348:
345:
342:
337:
333:
315:
312:
292:
291:
288:
282:
272:
252:
251:Problems in NC
249:
217:Equivalently,
144:Nick Pippenger
71:
55:
48:
45:
38:
35:
22:
16:
13:
10:
9:
6:
4:
3:
2:
3128:
3117:
3114:
3112:
3109:
3108:
3106:
3093:
3088:
3082:
3079:
3077:
3074:
3072:
3069:
3067:
3064:
3062:
3059:
3057:
3054:
3053:
3051:
3047:
3041:
3038:
3036:
3033:
3031:
3028:
3026:
3023:
3021:
3018:
3017:
3015:
3011:
3005:
3002:
3000:
2997:
2995:
2992:
2990:
2987:
2985:
2982:
2980:
2977:
2975:
2972:
2970:
2967:
2965:
2962:
2961:
2959:
2955:
2947:
2944:
2943:
2942:
2939:
2937:
2934:
2930:
2927:
2926:
2925:
2922:
2920:
2917:
2915:
2912:
2910:
2907:
2905:
2902:
2900:
2897:
2895:
2892:
2890:
2887:
2883:
2880:
2878:
2875:
2873:
2870:
2868:
2865:
2864:
2863:
2860:
2858:
2855:
2854:
2852:
2848:
2842:
2839:
2837:
2834:
2832:
2829:
2827:
2824:
2822:
2819:
2817:
2814:
2810:
2807:
2806:
2805:
2802:
2800:
2797:
2795:
2792:
2790:
2787:
2783:
2780:
2779:
2778:
2775:
2773:
2770:
2768:
2765:
2763:
2760:
2758:
2755:
2753:
2750:
2748:
2745:
2743:
2740:
2738:
2735:
2734:
2732:
2728:
2724:
2717:
2712:
2710:
2705:
2703:
2698:
2697:
2694:
2686:
2682:
2678:
2676:3-540-64310-9
2672:
2668:
2664:
2663:
2657:
2653:
2649:
2645:
2643:3-7643-3719-2
2639:
2634:
2633:
2626:
2622:
2620:0-201-53082-1
2616:
2612:
2608:
2604:
2600:
2597:
2591:
2587:
2583:
2581:1-84628-297-7
2577:
2573:
2569:
2565:
2561:
2556:
2552:
2548:
2546:
2545:0-19-508591-4
2542:
2539:
2537:
2532:
2528:
2524:
2520:
2518:3-540-59436-1
2514:
2510:
2506:
2501:
2497:
2493:
2489:
2483:
2479:
2475:
2471:
2467:
2466:
2462:
2453:
2449:
2445:
2441:
2436:
2431:
2427:
2423:
2416:
2414:
2405:
2402:
2396:
2394:
2390:
2385:
2381:
2377:
2373:
2366:
2363:
2357:
2354:
2348:
2346:
2342:
2336:
2333:
2322:
2318:
2311:
2304:
2301:
2295:
2293:
2291:
2287:
2281:
2278:
2273:
2269:
2265:
2261:
2257:
2253:
2249:
2245:
2238:
2235:
2230:
2226:
2221:
2216:
2212:
2208:
2204:
2197:
2194:
2189:
2185:
2181:
2177:
2170:
2167:
2160:
2158:
2156:
2150:
2148:
2140:
2122:
2118:
2100:
2096:
2081:
2078:
2074:
2069:
2061:
2053:
2045:
2041:
2038:for circuits
2036:
2032:
2027:
2023:
2020:
2016:
2008:
2004:
1996:
1992:
1988:
1984:
1970:
1963:
1959:
1958:
1957:
1955:
1951:
1947:
1943:
1938:
1934:
1927:
1923:
1918:
1910:
1895:
1892:
1888:
1884:
1864:
1862:
1858:
1846:
1841:
1827:
1821:
1816:
1806:
1791:
1787:
1775:
1773:
1768:
1766:
1756:
1754:
1749:
1743:
1739:
1736:
1732:
1728:
1724:
1722:
1717:
1715:
1710:
1708:
1704:
1700:
1696:
1691:
1689:
1685:
1667:
1663:
1659:
1656:
1634:
1630:
1626:
1623:
1601:
1597:
1593:
1590:
1582:
1578:
1574:
1570:
1566:
1562:
1558:
1554:
1550:
1546:
1542:
1538:
1534:
1530:
1526:
1522:
1518:
1514:
1510:
1506:
1502:
1498:
1494:
1490:
1486:
1482:
1478:
1468:
1466:
1458:
1456:
1429:
1426:
1421:
1418:
1415:
1400:
1397:
1394:
1389:
1374:
1371:
1368:
1363:
1344:
1320:
1317:
1312:
1309:
1306:
1291:
1288:
1285:
1280:
1265:
1262:
1259:
1254:
1235:
1234:
1233:
1231:
1227:
1208:
1205:
1200:
1185:
1180:
1161:
1160:
1159:
1157:
1153:
1149:
1145:
1142: ≥
1141:
1137:
1133:
1129:
1125:
1121:
1117:
1113:
1105:
1103:
1084:
1078:
1070:
1067:
1064:
1053:
1049:
1045:
1041:
1036:
1034:
1030:
1026:
1007:
1002:
999:
996:
981:
976:
961:
956:
937:
936:
935:
933:
914:
904:
899:
884:
879:
864:
851:
841:
836:
817:
816:
815:
813:
812:
807:
806:
801:
800:
795:
790:
788:
759:
756:
751:
736:
733:
730:
725:
710:
705:
686:
685:
684:
682:
678:
672:
668:
663:
656:
654:
635:
631:
627:
622:
618:
608:
600:
596:
589:
584:
580:
568:
550:
546:
523:
519:
492:
486:
483:
480:
474:
466:
445:
441:
437:
434:
431:
426:
423:
418:
415:
409:
402:
393:
390:
385:
381:
378:
375:
370:
366:
359:
354:
350:
346:
343:
340:
335:
331:
322:
313:
311:
309:
305:
301:
297:
289:
287:
283:
280:
276:
273:
270:
269:
268:
266:
262:
258:
250:
248:
246:
242:
238:
236:
232:
228:
224:
220:
215:
213:
209:
205:
201:
196:
194:
191:, when using
190:
189:
184:
183:
178:
174:
170:
166:
162:
158:
154:
153:
147:
145:
141:
135:
131:
124:
120:
119:
113:
109:
105:
101:
97:
93:
90:decidable in
89:
85:
81:
74:
46:
43:
2788:
2661:
2631:
2610:
2606:
2595:
2567:
2554:
2535:
2504:
2473:
2425:
2421:
2412:
2404:
2375:
2371:
2365:
2356:
2335:
2324:. Retrieved
2316:
2303:
2280:
2247:
2237:
2210:
2206:
2196:
2188:the original
2183:
2179:
2169:
2154:
2152:
2146:
2138:
2127:
2120:
2116:
2098:
2094:
2079:
2076:
2072:
2067:
2059:
2051:
2043:
2039:
2034:
2030:
2025:
2018:
2014:
2013:-computing ¬
2006:
2002:
1994:
1990:
1986:
1965:
1961:
1953:
1949:
1945:
1941:
1936:
1932:
1925:
1921:
1919:
1916:
1893:
1890:
1886:
1866:
1860:
1856:
1842:
1825:
1823:
1814:
1804:
1789:
1785:
1777:
1771:
1769:
1764:
1762:
1750:
1737:
1730:
1726:
1725:
1720:
1718:
1713:
1711:
1706:
1702:
1698:
1694:
1692:
1687:
1683:
1580:
1576:
1572:
1568:
1564:
1560:
1556:
1552:
1548:
1544:
1540:
1536:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1500:
1496:
1492:
1488:
1484:
1480:
1476:
1474:
1464:
1462:
1454:
1229:
1225:
1223:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1109:
1054:) space and
1051:
1047:
1039:
1037:
1032:
1028:
1024:
1022:
931:
929:
809:
803:
797:
793:
791:
789:-hierarchy.
786:
784:
680:
676:
670:
666:
661:
660:
317:
293:
264:
260:
256:
254:
244:
240:
239:
230:
226:
218:
216:
207:
199:
197:
192:
186:
180:
176:
172:
168:
164:
160:
150:
148:
140:Stephen Cook
133:
129:
122:
116:
111:
107:
103:
99:
83:
82:, the class
77:
2929:#P-complete
2867:NP-complete
2782:NL-complete
2250:: 307–311.
2213:(1): 2–22.
2124:by Lemma 1.
2114:-computing
2092:-computing
2001:-computing
1733:is exactly
1487:and length
465:binary tree
182:NP-complete
3105:Categories
2984:ELEMENTARY
2809:P-complete
2685:0931.68055
2652:0816.68086
2590:1102.68025
2527:1016.94046
2496:1193.68112
2463:References
2452:0667.68059
2326:2021-11-11
2102:. Because
1883:commutator
1735:nonuniform
1729:says that
934:, we have
467:of length
188:P-complete
2979:2-EXPTIME
2444:0022-0000
2264:0272-5428
2229:0019-9958
2066:-compute
2058:-compute
2050:-compute
1989:outputs ¬
1845:conjugate
1660:∈
1627:⊂
1594:⊂
1430:⋯
1398:⋯
1375:⊂
1372:⋯
1369:⊂
1321:⋯
1318:⊂
1292:⊂
1289:⋯
1286:⊂
1266:⊂
1263:⋯
1260:⊂
1209:⋯
1206:⊆
1186:⊆
1126:for some
1068:
982:⊆
962:⊆
905:⊆
885:⊆
865:⊆
852:⊆
842:⊆
760:⋯
757:⊆
737:⊆
734:⋯
731:⊆
711:⊆
628:∧
615:¬
609:∨
593:¬
590:∧
435:⋯
379:⋯
344:⋯
2974:EXPSPACE
2969:NEXPTIME
2737:DLOGTIME
2566:(2006).
2553:(1992).
2028:outputs
1709:inputs.
1515:≤
1507:) where
1138:for all
321:addition
255:As with
2964:EXPTIME
2872:NP-hard
2272:7029313
1868:Lemma 2
1779:Lemma 1
1581:accepts
1519:), and
1130:, then
314:Example
306:with a
281:, rank;
279:inverse
233:) with
68:
24:
3071:NSPACE
3066:DSPACE
2941:PSPACE
2683:
2673:
2650:
2640:
2617:
2588:
2578:
2543:
2525:
2515:
2494:
2484:
2450:
2442:
2270:
2262:
2227:
1682:is in
1583:a set
679:((log
669:((log
159:), so
127:using
121:((log
102:is in
3061:NTIME
3056:DTIME
2877:co-NP
2418:(PDF)
2313:(PDF)
2268:S2CID
2161:Notes
1931:,...,
1914:Proof
1836:when
1577:yield
1563:) or
1479:with
1050:(log
1035:= 0.
94:on a
2889:TFNP
2671:ISBN
2638:ISBN
2615:ISBN
2576:ISBN
2541:ISBN
2513:ISBN
2482:ISBN
2440:ISSN
2260:ISSN
2225:ISSN
2106:and
2042:and
1731:BWBP
1721:BWBP
1690:.
1523:and
808:and
802:and
538:and
298:and
212:PRAM
204:PRAM
110:and
3004:ALL
2904:QMA
2894:FNP
2836:APX
2831:BQP
2826:BPP
2816:ZPP
2747:ACC
2681:Zbl
2648:Zbl
2609:".
2586:Zbl
2523:Zbl
2492:Zbl
2448:Zbl
2430:doi
2380:doi
2376:318
2252:doi
2215:doi
2077:γδγ
1944:of
1891:γδγ
1810:or
1555:to
1065:log
241:RNC
78:In
3107::
2999:RE
2989:PR
2936:IP
2924:#P
2919:PP
2914:⊕P
2909:PH
2899:AM
2862:NP
2857:UP
2841:FP
2821:RP
2799:CC
2794:SC
2789:NC
2777:NL
2772:FL
2767:RL
2762:SL
2752:TC
2742:AC
2679:.
2669:.
2646:.
2607:NC
2596:NC
2584:.
2574:.
2521:.
2511:.
2490:.
2480:.
2476:.
2446:.
2438:.
2426:38
2424:.
2420:.
2413:NC
2392:^
2374:.
2344:^
2319:.
2315:.
2289:^
2266:.
2258:.
2246:.
2223:.
2211:64
2205:.
2184:27
2182:.
2178:.
2062:,
2054:,
1956:.
1877:,
1851:,
1772:NC
1767:.
1765:NC
1748:.
1738:NC
1547:,
1543:,
1503:,
1499:,
1475:A
1465:NC
1459:NC
1226:NC
1156:NC
1152:NC
1150:=
1148:NC
1136:NC
1134:=
1132:NC
1124:NC
1122:=
1120:NC
1116:NC
1040:NC
1029:AC
1027:=
1025:NC
814:.
811:AC
805:NL
794:NC
787:NC
673:))
662:NC
653:.
310:.
265:NC
263:.
261:NC
245:NC
219:NC
208:NC
193:NC
175:=
173:NC
165:NC
161:NC
125:))
104:NC
84:NC
2994:R
2804:P
2757:L
2715:e
2708:t
2701:v
2687:.
2654:.
2623:.
2592:.
2557:.
2538:.
2529:.
2498:.
2454:.
2432::
2415:"
2386:.
2382::
2329:.
2274:.
2254::
2231:.
2217::
2155:d
2147:C
2142:5
2139:S
2137:∈
2135:α
2130:α
2121:B
2119:∧
2117:A
2112:α
2108:α
2104:ε
2099:B
2097:∧
2095:A
2090:ε
2086:ε
2080:δ
2075:=
2073:ε
2068:A
2064:γ
2060:B
2056:δ
2052:A
2048:γ
2044:B
2040:A
2035:B
2033:∧
2031:A
2026:C
2021:.
2019:C
2017:=
2015:A
2011:α
2007:A
2003:A
1999:α
1995:A
1991:A
1987:C
1980:α
1975:i
1973:x
1968:i
1966:x
1962:C
1954:C
1950:D
1946:C
1942:D
1937:n
1933:x
1929:1
1926:x
1922:C
1907:ε
1903:δ
1899:γ
1894:δ
1889:=
1887:ε
1879:δ
1875:γ
1861:C
1857:C
1853:β
1849:α
1838:C
1834:α
1830:C
1826:C
1818:α
1815:Q
1812:β
1808:α
1805:P
1802:β
1798:β
1794:α
1790:Q
1786:P
1746:5
1714:L
1707:n
1703:n
1699:n
1695:n
1688:F
1684:A
1668:n
1664:2
1657:x
1635:k
1631:k
1624:F
1602:n
1598:2
1591:A
1573:i
1569:x
1567:(
1565:q
1561:x
1559:(
1557:p
1553:x
1549:q
1545:p
1541:i
1537:k
1533:k
1529:k
1525:q
1521:p
1517:n
1513:i
1509:i
1505:q
1501:p
1497:i
1493:m
1489:m
1485:k
1481:n
1438:C
1435:N
1427:=
1422:j
1419:+
1416:i
1410:C
1407:N
1401:=
1395:=
1390:i
1384:C
1381:N
1364:1
1358:C
1355:N
1329:C
1326:N
1313:j
1310:+
1307:i
1301:C
1298:N
1281:i
1275:C
1272:N
1255:1
1249:C
1246:N
1230:i
1201:2
1195:C
1192:N
1181:1
1175:C
1172:N
1144:i
1140:j
1128:i
1088:)
1085:1
1082:(
1079:O
1075:)
1071:n
1062:(
1052:n
1048:O
1033:i
1008:.
1003:1
1000:+
997:i
991:C
988:N
977:i
971:C
968:A
957:i
951:C
948:N
932:i
915:.
910:P
900:2
894:C
891:N
880:1
874:C
871:A
860:L
857:N
847:L
837:1
831:C
828:N
799:L
768:C
765:N
752:i
746:C
743:N
726:2
720:C
717:N
706:1
700:C
697:N
681:n
677:O
671:n
667:O
641:)
636:j
632:x
623:i
619:x
612:(
606:)
601:j
597:x
585:i
581:x
577:(
551:j
547:x
524:i
520:x
499:)
496:)
493:n
490:(
487:g
484:o
481:l
478:(
475:O
451:)
446:n
442:x
438:+
432:+
427:1
424:+
419:2
416:n
410:x
406:(
403:+
400:)
394:2
391:n
386:x
382:+
376:+
371:1
367:x
363:(
360:=
355:n
351:x
347:+
341:+
336:1
332:x
257:P
231:n
227:n
202:(
177:P
169:P
152:P
136:)
134:n
132:(
130:O
123:n
118:O
112:k
108:c
100:n
54:P
47:?
44:=
37:C
34:N
20::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.