17:
20:
Diagram of an AC circuit: The n input bits are on the bottom and the top gate produces the output; the circuit consists of AND- and OR-gates of polynomial fan-in each, and the alternation depth is bounded by a
136:
of the input bits (unlike the aforementioned addition/subtraction problems above which had two inputs) cannot be decided by any AC circuits, even with non-uniformity. It follows that AC is not equal to
69:
Integer addition and subtraction are computable in AC, but multiplication is not (specifically, when the inputs are two integers under the usual binary or base-10 representations of integers).
264:
381:
203:
743:
374:
253:
236:
IAS/PCMI Summer
Session 2000, Clay Mathematics Undergraduate Program: Basic Course on Computational Complexity
783:
778:
367:
143:, because a family of circuits in the latter class can compute parity. More precise bounds follow from
759:
566:
191:
40:
hierarchy, and consists of all families of circuits of depth O(1) and polynomial size, with unlimited-
748:
298:
97:
702:
292:
228:
195:
89:
697:
692:
183:
687:
341:
148:
349:
213:
8:
33:
707:
199:
184:
56:
671:
561:
493:
483:
390:
345:
329:
209:
29:
666:
656:
613:
603:
596:
586:
576:
534:
529:
524:
508:
488:
466:
461:
456:
444:
439:
434:
429:
337:
144:
138:
133:
117:
105:
101:
37:
147:. Using them, it has been shown that there is an oracle separation between the
661:
549:
471:
424:
317:
129:
113:
77:
772:
313:
288:
179:
109:
16:
249:
539:
449:
651:
476:
333:
646:
359:
641:
636:
581:
404:
93:
52:
44:
631:
48:
738:
733:
608:
591:
320:(1984). "Parity, circuits, and the polynomial-time hierarchy".
152:
73:
728:
723:
544:
41:
556:
414:
108:
describable in first-order logic with the addition of the
571:
503:
498:
419:
227:
Barrington, David Mix; Maciel, Alexis (July 18, 2000).
61:, which has only bounded-fanin AND and OR gates.
770:
226:
311:
375:
229:"Lecture 2: The Complexity of Some Problems"
186:Computational complexity. A modern approach
382:
368:
248:
178:
83:
287:
15:
55:only at the inputs). It thus contains
771:
389:
112:, or alternatively by FO(+, ×), or by
363:
100:AC is equal to the descriptive class
174:
172:
170:
168:
261:E0 309: Topics in Complexity Theory
64:
36:. It is the smallest class in the
13:
72:Since it is a circuit class, like
14:
795:
744:Probabilistically checkable proof
165:
270:from the original on 2021-10-16
305:
281:
242:
220:
123:
1:
158:
132:showed that calculating the
7:
322:Mathematical Systems Theory
10:
800:
760:List of complexity classes
192:Cambridge University Press
757:
716:
680:
624:
517:
397:
128:In 1984 Furst, Saxe, and
76:, AC also contains every
749:Interactive proof system
254:"Lecture 5: Feb 4, 2015"
252:; Hegde, Sumant (2015).
703:Arithmetical hierarchy
294:Descriptive Complexity
182:; Barak, Boaz (2009).
90:descriptive complexity
84:Descriptive complexity
22:
698:Grzegorczyk hierarchy
693:Exponential hierarchy
625:Considered infeasible
118:logarithmic hierarchy
19:
688:Polynomial hierarchy
518:Suspected infeasible
297:. Springer. p.
149:polynomial hierarchy
717:Families of classes
398:Considered feasible
784:Complexity classes
779:Circuit complexity
391:Complexity classes
334:10.1007/BF01744431
34:circuit complexity
23:
766:
765:
708:Boolean hierarchy
681:Class hierarchies
205:978-0-521-42426-4
791:
384:
377:
370:
361:
360:
354:
353:
312:Furst, Merrick;
309:
303:
302:
285:
279:
278:
276:
275:
269:
258:
246:
240:
239:
233:
224:
218:
217:
189:
176:
65:Example problems
30:complexity class
799:
798:
794:
793:
792:
790:
789:
788:
769:
768:
767:
762:
753:
712:
676:
620:
614:PSPACE-complete
513:
393:
388:
358:
357:
318:Sipser, Michael
310:
306:
286:
282:
273:
271:
267:
256:
247:
243:
231:
225:
221:
206:
177:
166:
161:
145:switching lemma
126:
86:
67:
12:
11:
5:
797:
787:
786:
781:
764:
763:
758:
755:
754:
752:
751:
746:
741:
736:
731:
726:
720:
718:
714:
713:
711:
710:
705:
700:
695:
690:
684:
682:
678:
677:
675:
674:
669:
664:
659:
654:
649:
644:
639:
634:
628:
626:
622:
621:
619:
618:
617:
616:
606:
601:
600:
599:
589:
584:
579:
574:
569:
564:
559:
554:
553:
552:
550:co-NP-complete
547:
542:
537:
527:
521:
519:
515:
514:
512:
511:
506:
501:
496:
491:
486:
481:
480:
479:
469:
464:
459:
454:
453:
452:
442:
437:
432:
427:
422:
417:
412:
407:
401:
399:
395:
394:
387:
386:
379:
372:
364:
356:
355:
314:Saxe, James B.
304:
280:
241:
219:
204:
180:Arora, Sanjeev
163:
162:
160:
157:
125:
122:
114:Turing machine
85:
82:
78:unary language
66:
63:
9:
6:
4:
3:
2:
796:
785:
782:
780:
777:
776:
774:
761:
756:
750:
747:
745:
742:
740:
737:
735:
732:
730:
727:
725:
722:
721:
719:
715:
709:
706:
704:
701:
699:
696:
694:
691:
689:
686:
685:
683:
679:
673:
670:
668:
665:
663:
660:
658:
655:
653:
650:
648:
645:
643:
640:
638:
635:
633:
630:
629:
627:
623:
615:
612:
611:
610:
607:
605:
602:
598:
595:
594:
593:
590:
588:
585:
583:
580:
578:
575:
573:
570:
568:
565:
563:
560:
558:
555:
551:
548:
546:
543:
541:
538:
536:
533:
532:
531:
528:
526:
523:
522:
520:
516:
510:
507:
505:
502:
500:
497:
495:
492:
490:
487:
485:
482:
478:
475:
474:
473:
470:
468:
465:
463:
460:
458:
455:
451:
448:
447:
446:
443:
441:
438:
436:
433:
431:
428:
426:
423:
421:
418:
416:
413:
411:
408:
406:
403:
402:
400:
396:
392:
385:
380:
378:
373:
371:
366:
365:
362:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
308:
300:
296:
295:
290:
284:
266:
262:
255:
251:
250:Kayal, Neeraj
245:
237:
230:
223:
215:
211:
207:
201:
197:
193:
188:
187:
181:
175:
173:
171:
169:
164:
156:
154:
150:
146:
142:
141:
135:
131:
121:
119:
115:
111:
110:BIT predicate
107:
103:
99:
95:
91:
81:
79:
75:
70:
62:
60:
59:
54:
50:
46:
43:
39:
35:
31:
27:
18:
409:
328:(1): 13–27.
325:
321:
307:
293:
289:Immerman, N.
283:
272:. Retrieved
260:
244:
235:
222:
185:
139:
127:
104:+BIT of all
87:
71:
68:
57:
25:
24:
597:#P-complete
535:NP-complete
450:NL-complete
198:–118, 287.
194:. pp.
124:Separations
92:viewpoint,
773:Categories
652:ELEMENTARY
477:P-complete
350:0534.94008
274:2021-10-16
214:1193.68112
159:References
51:(we allow
647:2-EXPTIME
106:languages
53:NOT gates
45:AND gates
21:constant.
642:EXPSPACE
637:NEXPTIME
405:DLOGTIME
291:(1999).
265:Archived
94:DLOGTIME
49:OR gates
32:used in
632:EXPTIME
540:NP-hard
342:0738749
116:in the
98:uniform
88:From a
739:NSPACE
734:DSPACE
609:PSPACE
348:
340:
212:
202:
153:PSPACE
134:parity
130:Sipser
74:P/poly
729:NTIME
724:DTIME
545:co-NP
268:(PDF)
257:(PDF)
232:(PDF)
42:fanin
28:is a
557:TFNP
200:ISBN
151:and
47:and
672:ALL
572:QMA
562:FNP
504:APX
499:BQP
494:BPP
484:ZPP
415:ACC
346:Zbl
330:doi
210:Zbl
196:117
775::
667:RE
657:PR
604:IP
592:#P
587:PP
582:⊕P
577:PH
567:AM
530:NP
525:UP
509:FP
489:RP
467:CC
462:SC
457:NC
445:NL
440:FL
435:RL
430:SL
420:TC
410:AC
344:.
338:MR
336:.
326:17
324:.
316:;
299:85
263:.
259:.
234:.
208:.
190:.
167:^
155:.
140:NC
120:.
102:FO
80:.
58:NC
38:AC
26:AC
662:R
472:P
425:L
383:e
376:t
369:v
352:.
332::
301:.
277:.
238:.
216:.
96:-
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
