1003:. They are complete in sense that they can perform any deterministic algorithm. However, it just happens that this is not all there is. In the physical world we also encounter randomness, notable in small systems governed by quantization effects, which is described by theory of Quantum Mechanics. Logic circuits cannot produce any randomness, and in that sense they form an incomplete logic set. Remedy to that is found in adding an ad-hoc random bit generator to logic networks, or computers, such as in
31:
1011:, which completes the set. It conveniently packs randomness and is inter-operable with deterministic Boolean logic circuits. However, an algebraic structure equivalent of Boolean algebra and associated methods of circuit construction and reduction for the extended set is yet unknown.
962:
depth. The class AC is defined similarly to NC, however gates are allowed to have unbounded fan-in (that is, the AND and OR gates can be applied to more than two bits). NC is an important class because it turns out that it represents the class of languages that have efficient
864:
P/poly) because there are undecidable problems that are in P/poly. P/poly turns out to have a number of properties that make it highly useful in the study of the relationships between complexity classes. In particular, it is helpful in investigating problems related to
240:) contain strings of different lengths, so languages cannot be fully captured by a single circuit (in contrast to the Turing machine model, in which a language is fully described by a single Turing machine). A language is instead represented by a
542:
can be defined on
Boolean circuits, including circuit depth, circuit size, and the number of alternations between AND gates and OR gates. For example, the size complexity of a Boolean circuit is the number of gates in the circuit.
843:
P/poly. In other words, any problem that can be computed in polynomial time by a deterministic Turing machine can also be computed by a polynomial-size circuit family. It is further the case that the inclusion is proper (i.e.
998:
Logic circuits are physical representation of simple logic operations, AND, OR and NOT (and their combinations, such as non-sequential flip-flops or circuit networks), that form a mathematical structure known as
958:
from an input node to the output node. The class NC is the set of languages that can be solved by circuit families that are restricted not only to having polynomial-size but also to having
659:
929:
313:
773:
603:
935:". P/poly also has the interesting feature that it can be equivalently defined as the class of languages recognized by a polynomial-time Turing machine with a polynomial-bounded
862:
818:
704:
990:. Therefore, this problem is considered to be "inherently sequential" in the sense that there is likely no efficient, highly parallel algorithm that solves the problem.
841:
482:
887:
340:
1205:
623:
522:
502:
440:
420:
400:
380:
360:
1437:
181:
nodes which are labeled as the outputs. The edges must also have some ordering, to distinguish between different arguments to the same
Boolean function.
1090:
1640:
1475:
1377:
554:), also has a small circuit complexity (that is, requires relatively few Boolean operations). Formally, it can be shown that if a language is in
1480:
1128:
1100:
1312:
1650:
1425:
1324:
524:. In other words, a language is the set of strings which, when applied to the circuits corresponding to their lengths, evaluate to 1.
1359:
1198:
1067:
724:, the set of languages that are decidable by polynomial-size circuit families. It follows directly from the fact that languages in
1371:
1307:
539:
39:
34:
Example
Boolean circuit. The ∧ nodes are AND gates, the ∨ nodes are OR gates, and the ¬ nodes are NOT gates
1497:
1365:
1191:
1004:
196:
of 1. Thus, a
Boolean circuit can be regarded as a generalization that allows shared subformulas and multiple outputs.
1614:
1509:
126:
628:
1529:
1487:
550:. Intuitively, a language with small time complexity (that is, requires relatively few sequential operations on a
1645:
1430:
1415:
1341:
1301:
233:
161:
of
Boolean functions, corresponding to the gates allowable in the circuit model. A Boolean circuit over a basis
1442:
1347:
1335:
900:
138:
125:. They are an abstraction that omits many aspects relevant to designing real digital logic circuits, such as
247:
1492:
1270:
1265:
727:
720:
Several important complexity classes are defined in terms of
Boolean circuits. The most general of these is
557:
212:
1586:
1383:
1020:
174:
177:. Each vertex corresponds to either a basis function or one of the inputs, and there is a set of exactly
1598:
1552:
1420:
1318:
1255:
976:
185:
118:
154:
1524:
1519:
1502:
1222:
890:
106:
51:
1571:
1514:
1353:
1275:
1250:
1214:
936:
931:. A full description of the relations between P/poly and other complexity classes is available at "
114:
58:
55:
1591:
1457:
1295:
1260:
1157:
1007:. A recent work has introduced a theoretical concept of an inherently random logic circuit named
964:
847:
778:
715:
664:
533:
189:
43:
826:
445:
1146:"Entropy considerations in improved circuits for a biologically-inspired random pulse computer"
950:. These classes are defined not only in terms of their circuit size but also in terms of their
1547:
1124:
1096:
1063:
142:
30:
1280:
1167:
987:
237:
122:
95:
65:
can be decided by a family of
Boolean circuits, one circuit for each possible input length.
872:
318:
1470:
1465:
1447:
1410:
1405:
1330:
1035:
1000:
959:
947:
943:
894:
547:
229:
84:
73:
62:
1400:
1086:
821:
608:
551:
507:
487:
425:
405:
385:
365:
345:
134:
1634:
1581:
1564:
1559:
1030:
980:
955:
979:— the problem of computing the output of a given Boolean circuit on a given input
942:
Two subclasses of P/poly that have interesting properties in their own right are
866:
110:
17:
1172:
1145:
1619:
1285:
1230:
1025:
984:
69:
192:
is a
Boolean circuit with a single output node in which every other node has
1576:
1245:
91:
869:. For example, if there is any language in NP that is not in P/poly then P
1240:
1235:
215:, i. e. from which all other Boolean functions can be constructed.
208:
200:
87:
76:
204:
193:
80:
1183:
932:
721:
130:
105:
Boolean circuits provide a model for many digital components used in
1162:
546:
There is a natural connection between circuit size complexity and
29:
228:
A particular circuit acts only on inputs of fixed size. However,
1187:
362:
input variables. A circuit family is said to decide a language
99:
889:
NP. P/poly also helps to investigate properties of the
954:. The depth of a circuit is the length of the longest
903:
875:
850:
829:
781:
730:
667:
631:
611:
560:
510:
490:
448:
428:
408:
388:
368:
348:
321:
250:
1607:
1540:
1456:
1393:
1221:
244:. A circuit family is an infinite list of circuits
153:In giving a formal definition of Boolean circuits,
72:they contain. For example, a circuit might contain
923:
881:
856:
835:
812:
767:
698:
653:
617:
597:
516:
496:
476:
434:
414:
394:
374:
354:
334:
307:
1095:(2nd ed.). USA: Thomson Course Technology.
199:A common basis for Boolean circuits is the set {
654:{\displaystyle t:\mathbb {N} \to \mathbb {N} }
1199:
68:Boolean circuits are defined in terms of the
8:
1114:
1112:
1121:Computational Complexity: A Modern Approach
1206:
1192:
1184:
1144:Stipčević, Mario; Batelić, Mateja (2022).
716:Complexity classes § Boolean circuits
1171:
1161:
1092:Introduction to the Theory of Computation
1053:
1051:
924:{\displaystyle \Sigma _{2}^{\mathsf {P}}}
914:
913:
908:
902:
874:
849:
828:
792:
780:
732:
731:
729:
678:
666:
647:
646:
639:
638:
630:
610:
562:
561:
559:
509:
489:
453:
447:
427:
407:
387:
367:
347:
326:
320:
284:
271:
258:
249:
1081:
1079:
1378:Application-specific integrated circuit
1047:
308:{\displaystyle (C_{0},C_{1},C_{2},...)}
915:
768:{\displaystyle {\mathsf {TIME}}(t(n))}
742:
739:
736:
733:
598:{\displaystyle {\mathsf {TIME}}(t(n))}
572:
569:
566:
563:
173:outputs, is then defined as a finite
90:, or be entirely described by binary
7:
1313:Three-dimensional integrated circuit
1119:Arora, Sanjeev; Barak, Boaz (2009).
102:as input and outputs a single bit.
1325:Erasable programmable logic device
1060:Introduction to Circuit Complexity
905:
157:starts by defining a basis as set
25:
1360:Complex programmable logic device
661:, then it has circuit complexity
94:. Each gate corresponds to some
1641:Computational complexity theory
1372:Field-programmable object array
1308:Mixed-signal integrated circuit
897:⊆ P/poly, then PH collapses to
40:computational complexity theory
1123:. Cambridge University Press.
807:
804:
798:
785:
762:
759:
753:
747:
693:
690:
684:
671:
643:
592:
589:
583:
577:
465:
459:
302:
251:
1:
1498:Hardware description language
1366:Field-programmable gate array
98:that takes a fixed number of
1005:Probabilistic Turing machine
1510:Formal equivalence checking
857:{\displaystyle \subsetneq }
813:{\displaystyle O(t^{2}(n))}
699:{\displaystyle O(t^{2}(n))}
1667:
1530:Hierarchical state machine
1488:Transaction-level modeling
1173:10.1038/s41598-021-04177-9
1058:Vollmer, Heribert (1999).
836:{\displaystyle \subseteq }
713:
531:
477:{\displaystyle C_{n}(w)=1}
1651:Logic in computer science
1431:Digital signal processing
1416:Logic in computer science
1342:Programmable logic device
1302:Hybrid integrated circuit
1443:Switching circuit theory
1348:Programmable Array Logic
1336:Programmable logic array
775:have circuit complexity
219:Computational complexity
1493:Register-transfer level
1384:Tensor Processing Unit
1021:Circuit satisfiability
925:
883:
858:
837:
814:
769:
700:
655:
619:
599:
518:
498:
478:
436:
416:
396:
376:
356:
336:
309:
175:directed acyclic graph
119:arithmetic logic units
59:digital logic circuits
35:
1599:Electronic literature
1553:Hardware acceleration
1421:Computer architecture
1319:Emitter-coupled logic
1256:Printed circuit board
977:Circuit Value Problem
926:
884:
882:{\displaystyle \neq }
859:
838:
815:
770:
701:
656:
620:
600:
519:
499:
479:
437:
417:
397:
382:if, for every string
377:
357:
337:
335:{\displaystyle C_{n}}
310:
213:functionally complete
186:propositional formula
184:As a special case, a
33:
1525:Finite-state machine
1503:High-level synthesis
1438:Circuit minimization
1062:. Berlin: Springer.
933:Importance of P/poly
901:
891:polynomial hierarchy
873:
848:
827:
779:
728:
665:
629:
609:
558:
508:
488:
446:
426:
406:
386:
366:
346:
319:
248:
107:computer engineering
27:Model of computation
1572:Digital photography
1354:Generic Array Logic
1276:Combinational logic
1251:Printed electronics
1215:Digital electronics
965:parallel algorithms
920:
540:complexity measures
528:Complexity measures
422:is in the language
236:representations of
121:, but they exclude
1520:Asynchronous logic
1296:Integrated circuit
1261:Electronic circuit
1150:Scientific Reports
971:Circuit evaluation
921:
904:
893:. For example, if
879:
854:
833:
810:
765:
710:Complexity classes
696:
651:
615:
595:
538:Several important
534:Circuit complexity
514:
494:
474:
432:
412:
392:
372:
352:
332:
305:
190:Boolean expression
50:is a mathematical
44:circuit complexity
36:
1628:
1627:
1577:Digital telephone
1548:Computer hardware
1515:Synchronous logic
1130:978-0-521-42426-4
1102:978-0-534-95097-2
618:{\displaystyle t}
517:{\displaystyle w}
504:is the length of
497:{\displaystyle n}
435:{\displaystyle L}
415:{\displaystyle w}
395:{\displaystyle w}
375:{\displaystyle L}
355:{\displaystyle n}
238:decision problems
149:Formal definition
143:propagation delay
139:power consumption
16:(Redirected from
1658:
1646:Digital circuits
1281:Sequential logic
1208:
1201:
1194:
1185:
1178:
1177:
1175:
1165:
1141:
1135:
1134:
1116:
1107:
1106:
1083:
1074:
1073:
1055:
1009:random flip-flop
988:decision problem
930:
928:
927:
922:
919:
918:
912:
888:
886:
885:
880:
863:
861:
860:
855:
842:
840:
839:
834:
819:
817:
816:
811:
797:
796:
774:
772:
771:
766:
746:
745:
705:
703:
702:
697:
683:
682:
660:
658:
657:
652:
650:
642:
624:
622:
621:
616:
604:
602:
601:
596:
576:
575:
523:
521:
520:
515:
503:
501:
500:
495:
483:
481:
480:
475:
458:
457:
441:
439:
438:
433:
421:
419:
418:
413:
401:
399:
398:
393:
381:
379:
378:
373:
361:
359:
358:
353:
341:
339:
338:
333:
331:
330:
314:
312:
311:
306:
289:
288:
276:
275:
263:
262:
230:formal languages
123:sequential logic
96:Boolean function
21:
18:Boolean circuits
1666:
1665:
1661:
1660:
1659:
1657:
1656:
1655:
1631:
1630:
1629:
1624:
1603:
1536:
1471:Place and route
1466:Logic synthesis
1452:
1448:Gate equivalent
1411:Logic synthesis
1406:Boolean algebra
1389:
1331:Macrocell array
1291:Boolean circuit
1217:
1212:
1182:
1181:
1143:
1142:
1138:
1131:
1118:
1117:
1110:
1103:
1087:Sipser, Michael
1085:
1084:
1077:
1070:
1057:
1056:
1049:
1044:
1036:Switching lemma
1017:
1001:Boolean algebra
996:
973:
960:polylogarithmic
937:advice function
899:
898:
871:
870:
846:
845:
825:
824:
788:
777:
776:
726:
725:
718:
712:
674:
663:
662:
627:
626:
607:
606:
556:
555:
548:time complexity
536:
530:
506:
505:
486:
485:
449:
444:
443:
442:if and only if
424:
423:
404:
403:
384:
383:
364:
363:
344:
343:
322:
317:
316:
280:
267:
254:
246:
245:
226:
221:
151:
63:formal language
48:Boolean circuit
28:
23:
22:
15:
12:
11:
5:
1664:
1662:
1654:
1653:
1648:
1643:
1633:
1632:
1626:
1625:
1623:
1622:
1617:
1611:
1609:
1605:
1604:
1602:
1601:
1596:
1595:
1594:
1589:
1587:cinematography
1579:
1574:
1569:
1568:
1567:
1557:
1556:
1555:
1544:
1542:
1538:
1537:
1535:
1534:
1533:
1532:
1522:
1517:
1512:
1507:
1506:
1505:
1500:
1490:
1485:
1484:
1483:
1478:
1468:
1462:
1460:
1454:
1453:
1451:
1450:
1445:
1440:
1435:
1434:
1433:
1426:Digital signal
1423:
1418:
1413:
1408:
1403:
1401:Digital signal
1397:
1395:
1391:
1390:
1388:
1387:
1381:
1375:
1369:
1363:
1357:
1351:
1345:
1339:
1333:
1328:
1322:
1316:
1310:
1305:
1299:
1293:
1288:
1283:
1278:
1273:
1268:
1263:
1258:
1253:
1248:
1243:
1238:
1233:
1227:
1225:
1219:
1218:
1213:
1211:
1210:
1203:
1196:
1188:
1180:
1179:
1136:
1129:
1108:
1101:
1075:
1068:
1046:
1045:
1043:
1040:
1039:
1038:
1033:
1028:
1023:
1016:
1013:
995:
992:
972:
969:
917:
911:
907:
878:
853:
832:
809:
806:
803:
800:
795:
791:
787:
784:
764:
761:
758:
755:
752:
749:
744:
741:
738:
735:
714:Main article:
711:
708:
695:
692:
689:
686:
681:
677:
673:
670:
649:
645:
641:
637:
634:
625:is a function
614:
594:
591:
588:
585:
582:
579:
574:
571:
568:
565:
552:Turing machine
529:
526:
513:
493:
473:
470:
467:
464:
461:
456:
452:
431:
411:
391:
371:
351:
329:
325:
304:
301:
298:
295:
292:
287:
283:
279:
274:
270:
266:
261:
257:
253:
242:circuit family
225:
222:
220:
217:
150:
147:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1663:
1652:
1649:
1647:
1644:
1642:
1639:
1638:
1636:
1621:
1618:
1616:
1615:Metastability
1613:
1612:
1610:
1608:Design issues
1606:
1600:
1597:
1593:
1590:
1588:
1585:
1584:
1583:
1582:Digital video
1580:
1578:
1575:
1573:
1570:
1566:
1563:
1562:
1561:
1560:Digital audio
1558:
1554:
1551:
1550:
1549:
1546:
1545:
1543:
1539:
1531:
1528:
1527:
1526:
1523:
1521:
1518:
1516:
1513:
1511:
1508:
1504:
1501:
1499:
1496:
1495:
1494:
1491:
1489:
1486:
1482:
1479:
1477:
1474:
1473:
1472:
1469:
1467:
1464:
1463:
1461:
1459:
1455:
1449:
1446:
1444:
1441:
1439:
1436:
1432:
1429:
1428:
1427:
1424:
1422:
1419:
1417:
1414:
1412:
1409:
1407:
1404:
1402:
1399:
1398:
1396:
1392:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1332:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1309:
1306:
1303:
1300:
1297:
1294:
1292:
1289:
1287:
1284:
1282:
1279:
1277:
1274:
1272:
1269:
1267:
1264:
1262:
1259:
1257:
1254:
1252:
1249:
1247:
1244:
1242:
1239:
1237:
1234:
1232:
1229:
1228:
1226:
1224:
1220:
1216:
1209:
1204:
1202:
1197:
1195:
1190:
1189:
1186:
1174:
1169:
1164:
1159:
1155:
1151:
1147:
1140:
1137:
1132:
1126:
1122:
1115:
1113:
1109:
1104:
1098:
1094:
1093:
1088:
1082:
1080:
1076:
1071:
1069:3-540-64310-9
1065:
1061:
1054:
1052:
1048:
1041:
1037:
1034:
1032:
1031:Boolean logic
1029:
1027:
1024:
1022:
1019:
1018:
1014:
1012:
1010:
1006:
1002:
993:
991:
989:
986:
982:
978:
970:
968:
966:
961:
957:
956:directed path
953:
949:
945:
940:
938:
934:
909:
896:
892:
876:
868:
851:
830:
823:
801:
793:
789:
782:
756:
750:
723:
717:
709:
707:
687:
679:
675:
668:
635:
632:
612:
586:
580:
553:
549:
544:
541:
535:
527:
525:
511:
491:
471:
468:
462:
454:
450:
429:
409:
389:
369:
349:
327:
323:
299:
296:
293:
290:
285:
281:
277:
272:
268:
264:
259:
255:
243:
239:
235:
231:
223:
218:
216:
214:
210:
206:
202:
197:
195:
191:
187:
182:
180:
176:
172:
168:
164:
160:
156:
148:
146:
145:variability.
144:
140:
136:
132:
128:
127:metastability
124:
120:
116:
112:
108:
103:
101:
97:
93:
89:
86:
82:
78:
75:
71:
66:
64:
60:
57:
56:combinational
53:
49:
45:
41:
32:
19:
1541:Applications
1290:
1153:
1149:
1139:
1120:
1091:
1059:
1008:
997:
994:Completeness
974:
951:
941:
719:
545:
537:
241:
234:string-based
227:
211:}, which is
198:
183:
178:
170:
166:
162:
158:
152:
111:multiplexers
109:, including
104:
67:
47:
37:
1271:Memory cell
867:P versus NP
169:inputs and
70:logic gates
1635:Categories
1620:Runt pulse
1592:television
1286:Logic gate
1231:Transistor
1223:Components
1163:1908.04779
1026:Logic gate
985:P-complete
532:See also:
224:Background
92:NAND gates
1476:Placement
1266:Flip-flop
1246:Capacitor
1042:Footnotes
906:Σ
877:≠
852:⊊
831:⊆
644:→
88:NOT gates
1241:Inductor
1236:Resistor
1089:(2006).
1015:See also
605:, where
484:, where
315:, where
135:glitches
81:OR gates
1481:Routing
1315:(3D IC)
1156:: 115.
983:— is a
194:fan-out
165:, with
155:Vollmer
1458:Design
1394:Theory
1380:(ASIC)
1374:(FPOA)
1368:(FPGA)
1362:(CPLD)
1327:(EPLD)
1127:
1099:
1066:
981:string
722:P/poly
141:, and
131:fanout
117:, and
115:adders
74:binary
1565:radio
1386:(TPU)
1356:(GAL)
1350:(PAL)
1344:(PLD)
1338:(PLA)
1321:(ECL)
1304:(HIC)
1158:arXiv
952:depth
820:that
232:(the
85:unary
52:model
1298:(IC)
1125:ISBN
1097:ISBN
1064:ISBN
975:The
946:and
342:has
100:bits
83:and
79:and
61:. A
54:for
46:, a
42:and
1168:doi
209:NOT
201:AND
188:or
77:AND
38:In
1637::
1166:.
1154:12
1152:.
1148:.
1111:^
1078:^
1050:^
967:.
948:AC
944:NC
939:.
895:NP
706:.
402:,
207:,
205:OR
203:,
137:,
133:,
129:,
113:,
1207:e
1200:t
1193:v
1176:.
1170::
1160::
1133:.
1105:.
1072:.
916:P
910:2
844:P
822:P
808:)
805:)
802:n
799:(
794:2
790:t
786:(
783:O
763:)
760:)
757:n
754:(
751:t
748:(
743:E
740:M
737:I
734:T
694:)
691:)
688:n
685:(
680:2
676:t
672:(
669:O
648:N
640:N
636::
633:t
613:t
593:)
590:)
587:n
584:(
581:t
578:(
573:E
570:M
567:I
564:T
512:w
492:n
472:1
469:=
466:)
463:w
460:(
455:n
451:C
430:L
410:w
390:w
370:L
350:n
328:n
324:C
303:)
300:.
297:.
294:.
291:,
286:2
282:C
278:,
273:1
269:C
265:,
260:0
256:C
252:(
179:m
171:m
167:n
163:B
159:B
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
