684:
Restricted Case of CVP – Like CVP, except each gate has two inputs and two outputs (F and Not F), every other layer is just AND gates, the rest are OR gates (or, equivalently, all gates are NAND gates, or all gates are NOR gates), the inputs of a gate come from the immediately preceding
578:
steps if and only if x is in L. Clearly, if we can parallelize a general simulation of a sequential computer (ie. The Turing machine simulation of a Turing machine), then we will be able to parallelize any program that runs on that computer. If this problem is in
178:
contains all problems that can be solved by a sequential computer in logarithmic space. Such machines run in polynomial time because they can have a polynomial number of configurations. It is suspected that
145:, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine. It is not known whether
537:
71:
The specific type of reduction used varies and may affect the exact set of problems. Generically, reductions stronger than polynomial-time reductions are used, since all languages in
364:
595:-completeness. We aren't really interested in whether a problem can be solved quickly on a parallel machine. We're just interested in whether a parallel machine solves it
433:
842:
576:
460:
480:
388:
318:
651:
in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time. That puts the sequential problem in
206:-complete problems, viewed as the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the
153:. In other words, it is not known whether there are any tractable problems that are inherently sequential. Just as it is widely suspected that
1013:
390:
in P, output the encoding of the Turing machine which accepts it in polynomial-time, the encoding of x itself, and a number of steps
666:-complete, and therefore are widely believed to be inherently sequential. These include the following problems which are
1375:
971:
1006:
599:
quickly than a sequential machine. Therefore, we have to reword the problem so that the sequential version is in
17:
485:
736:
187:; that is, that some problems that can be solved in polynomial time also require more than logarithmic space.
982:
331:
141:, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class
908:-complete problem may have different time complexities, this fact does not imply that all the problems in
226:. It can also be thought of as the "problems requiring superlogarithmic space"; a log-space solution to a
1410:
999:
1391:
1198:
1380:
743:
435:
corresponding to the p which is there polynomial-time bound on the operation of the Turing
Machine
1334:
47:
670:-complete under at least logspace reductions, either as given, or in a decision-problem form:
393:
68:
specifically when stronger notions of reducibility than polytime-reducibility are considered.
1329:
1324:
893:
674:
612:
29:
817:
681:, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.
542:
1319:
718:
438:
325:
86:
8:
724:
106:
688:
465:
373:
303:
241:
The logic behind this is analogous to the logic that a polynomial-time solution to an
1339:
967:
1303:
1193:
1125:
1115:
1022:
941:
901:
588:
230:-complete problem (using the definition based on log-space reductions) would imply
21:
1298:
1288:
1245:
1235:
1228:
1218:
1208:
1166:
1161:
1156:
1140:
1120:
1098:
1093:
1088:
1076:
1071:
1066:
1061:
889:
867:
803:
757:
678:
627:), then the obvious sequential algorithm can take time 2. On the other hand, if
81:
1293:
1181:
1103:
1056:
795:
298:
174:
114:
33:
97:
and so cannot be effectively parallelized, under the unproven assumption that
1404:
866:
and D. Sivakumar, building on work by
Ogihara, showed that if there exists a
946:
695:
297:-complete problem under logspace many-one reductions is following: given a
929:
844:
many-one reductions, DLOGTIME reductions, or polylogarithmic projections.
1171:
1081:
897:
799:
728:
191:
89:
on a parallel computer with a polynomial number of processors, then all
1283:
863:
214:
question. Finding an efficient way to parallelize the solution to some
1278:
991:
691:– Maximize a linear function subject to linear inequality constraints
974:. — Develops the theory, then catalogs 96 P-Complete problems.
814:-complete under even stronger notions of reduction, such as uniform
714:
in a depth-first search induced by the order of the adjacency lists?
1273:
1268:
1213:
1036:
273:. Similarly, if we have a log-space reduction from any problem in
1263:
930:"Sparse hard sets for P: resolution of a conjecture of Hartmanis"
75:(except the empty language and the language of all strings) are
1370:
1365:
1240:
1223:
731:, is there a variable assignment which satisfies them? This is
694:
Lexicographically First Depth First Search
Ordering – Given a
587:. If the number of steps is written in binary, the problem is
1360:
1355:
1176:
1188:
1046:
781:
777:
721:
and a string, can that string be generated by that grammar?
591:. This problem illustrates a common trick in the theory of
1203:
1135:
1130:
1051:
1041:
962:
Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995.
109:, this remains true, but additionally we learn that all
61:
which problems are difficult to parallelize effectively,
977:
Satoru Miyano, Shuji
Shiraishi, and Takayoshi Shoudai.
64:
which problems are difficult to solve in limited space.
366:
does that machine halt on that input within the first
79:-complete under polynomial-time reductions. If we use
964:
Limits To
Parallel computation; P-Completeness Theory
820:
784:, this is much easier, as the problem reduces to "Is
545:
488:
468:
441:
396:
376:
334:
306:
277:
to a problem A, and a log-space solution for A, then
85:
reductions, that is, reductions which can operate in
888:-complete problems may be solvable with different
836:
570:
531:
474:
454:
427:
382:
358:
312:
855:-complete, one typically tries to reduce a known
806:, determine whether this term has a partial type.
760:(1978 paradigm) Data Compression – given strings
742:Game of Life – Given an initial configuration of
1402:
57:decision problems is useful in the analysis of:
698:with fixed ordered adjacency lists, and nodes
1007:
927:
526:
489:
353:
335:
320:, an input for that machine x, and a number
662:Many other problems have been proved to be
1014:
1000:
847:In order to prove that a given problem in
717:Context Free Grammar Membership – Given a
631:is written as a unary number (a string of
532:{\displaystyle \langle M,x,p(|x|)\rangle }
117:under the weaker unproven assumption that
945:
904:. Of course, because the reductions to a
934:Journal of Computer and System Sciences
1403:
1021:
288:
995:
750:(in unary), is that cell alive after
659:if and only if it is parallelizable.
607:to be written in unary. If a number
603:. That is why this problem required
359:{\displaystyle \langle M,x,T\rangle }
859:-complete problem to the given one.
583:, then so is every other problem in
928:Cai, Jin-Yi; Sivakumar, D. (1999),
912:can also be solved in linear time.
50:to it by an appropriate reduction.
13:
776:to the dictionary? (Note that for
539:. The machine M halts on x within
218:-complete problem would show that
14:
1422:
1376:Probabilistically checkable proof
161:, so it is widely suspected that
810:Most of the languages above are
746:, a particular cell, and a time
113:-complete problems lie outside
93:-complete problems lie outside
18:computational complexity theory
921:
737:boolean satisfiability problem
565:
561:
553:
549:
523:
519:
511:
507:
422:
418:
410:
406:
257:reduction from any problem in
245:-complete problem would prove
125:. In this latter case the set
1:
979:A List of P-Complete Problems
956:
798:for partial types – Given an
132:
7:
643:), then it only takes time
10:
1427:
1392:List of complexity classes
129:-complete may be smaller.
1389:
1348:
1312:
1256:
1149:
1029:
105:. If we use the stronger
32:for the complexity class
1381:Interactive proof system
915:
772:with an LZ78 method add
428:{\displaystyle T=p(|x|)}
194:problems to analyze the
190:Similarly to the use of
655:. Then, it will be in
261:to a problem A, and an
1335:Arithmetical hierarchy
947:10.1006/jcss.1998.1615
838:
837:{\displaystyle AC^{0}}
710:visited before vertex
623: = log
619:ones and zeros, where
572:
571:{\displaystyle p(|x|)}
533:
476:
456:
429:
384:
360:
314:
1330:Grzegorczyk hierarchy
1325:Exponential hierarchy
1257:Considered infeasible
981:. Kyushu University,
894:Circuit Value Problem
839:
744:Conway's Game of Life
675:Circuit Value Problem
573:
534:
477:
457:
455:{\displaystyle M_{L}}
430:
385:
370:steps? For any x in
361:
315:
265:solution for A, then
172:Similarly, the class
42:and every problem in
1320:Polynomial hierarchy
1150:Suspected infeasible
892:. For instance, the
818:
780:compression such as
719:context-free grammar
615:number (a string of
543:
486:
466:
439:
394:
374:
332:
304:
87:polylogarithmic time
1349:Families of classes
1030:Considered feasible
768:, will compressing
725:Horn-satisfiability
289:P-complete problems
107:log-space reduction
1411:Complexity classes
1023:Complexity classes
834:
689:Linear programming
568:
529:
472:
452:
425:
380:
356:
310:
1398:
1397:
1340:Boolean hierarchy
1313:Class hierarchies
896:can be solved in
890:time complexities
735:s version of the
727:– given a set of
475:{\displaystyle L}
383:{\displaystyle L}
313:{\displaystyle M}
1418:
1016:
1009:
1002:
993:
992:
985:. December 1990.
951:
950:
949:
925:
902:topological sort
874:-complete, then
843:
841:
840:
835:
833:
832:
677:(CVP) – Given a
611:is written as a
589:EXPTIME-complete
577:
575:
574:
569:
564:
556:
538:
536:
535:
530:
522:
514:
481:
479:
478:
473:
461:
459:
458:
453:
451:
450:
434:
432:
431:
426:
421:
413:
389:
387:
386:
381:
365:
363:
362:
357:
319:
317:
316:
311:
22:decision problem
1426:
1425:
1421:
1420:
1419:
1417:
1416:
1415:
1401:
1400:
1399:
1394:
1385:
1344:
1308:
1252:
1246:PSPACE-complete
1145:
1025:
1020:
989:
959:
954:
926:
922:
918:
868:sparse language
828:
824:
819:
816:
815:
804:lambda calculus
758:LZW (algorithm)
560:
552:
544:
541:
540:
518:
510:
487:
484:
483:
467:
464:
463:
446:
442:
440:
437:
436:
417:
409:
395:
392:
391:
375:
372:
371:
333:
330:
329:
305:
302:
301:
293:The most basic
291:
253:: if we have a
165:does not equal
157:does not equal
135:
12:
11:
5:
1424:
1414:
1413:
1396:
1395:
1390:
1387:
1386:
1384:
1383:
1378:
1373:
1368:
1363:
1358:
1352:
1350:
1346:
1345:
1343:
1342:
1337:
1332:
1327:
1322:
1316:
1314:
1310:
1309:
1307:
1306:
1301:
1296:
1291:
1286:
1281:
1276:
1271:
1266:
1260:
1258:
1254:
1253:
1251:
1250:
1249:
1248:
1238:
1233:
1232:
1231:
1221:
1216:
1211:
1206:
1201:
1196:
1191:
1186:
1185:
1184:
1182:co-NP-complete
1179:
1174:
1169:
1159:
1153:
1151:
1147:
1146:
1144:
1143:
1138:
1133:
1128:
1123:
1118:
1113:
1112:
1111:
1101:
1096:
1091:
1086:
1085:
1084:
1074:
1069:
1064:
1059:
1054:
1049:
1044:
1039:
1033:
1031:
1027:
1026:
1019:
1018:
1011:
1004:
996:
987:
986:
983:RIFIS-TR-CS-17
975:
958:
955:
953:
952:
940:(2): 280–296,
919:
917:
914:
831:
827:
823:
808:
807:
802:term from the
796:Type inference
793:
755:
740:
722:
715:
692:
686:
682:
647:. By writing
567:
563:
559:
555:
551:
548:
528:
525:
521:
517:
513:
509:
506:
503:
500:
497:
494:
491:
471:
449:
445:
424:
420:
416:
412:
408:
405:
402:
399:
379:
355:
352:
349:
346:
343:
340:
337:
309:
299:Turing machine
290:
287:
202:question, the
134:
131:
66:
65:
62:
53:The notion of
38:) if it is in
9:
6:
4:
3:
2:
1423:
1412:
1409:
1408:
1406:
1393:
1388:
1382:
1379:
1377:
1374:
1372:
1369:
1367:
1364:
1362:
1359:
1357:
1354:
1353:
1351:
1347:
1341:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1321:
1318:
1317:
1315:
1311:
1305:
1302:
1300:
1297:
1295:
1292:
1290:
1287:
1285:
1282:
1280:
1277:
1275:
1272:
1270:
1267:
1265:
1262:
1261:
1259:
1255:
1247:
1244:
1243:
1242:
1239:
1237:
1234:
1230:
1227:
1226:
1225:
1222:
1220:
1217:
1215:
1212:
1210:
1207:
1205:
1202:
1200:
1197:
1195:
1192:
1190:
1187:
1183:
1180:
1178:
1175:
1173:
1170:
1168:
1165:
1164:
1163:
1160:
1158:
1155:
1154:
1152:
1148:
1142:
1139:
1137:
1134:
1132:
1129:
1127:
1124:
1122:
1119:
1117:
1114:
1110:
1107:
1106:
1105:
1102:
1100:
1097:
1095:
1092:
1090:
1087:
1083:
1080:
1079:
1078:
1075:
1073:
1070:
1068:
1065:
1063:
1060:
1058:
1055:
1053:
1050:
1048:
1045:
1043:
1040:
1038:
1035:
1034:
1032:
1028:
1024:
1017:
1012:
1010:
1005:
1003:
998:
997:
994:
990:
984:
980:
976:
973:
972:0-19-508591-4
969:
965:
961:
960:
948:
943:
939:
935:
931:
924:
920:
913:
911:
907:
903:
899:
895:
891:
887:
883:
881:
878: =
877:
873:
869:
865:
860:
858:
854:
850:
845:
829:
825:
821:
813:
805:
801:
797:
794:
791:
787:
783:
779:
775:
771:
767:
763:
759:
756:
753:
749:
745:
741:
738:
734:
730:
726:
723:
720:
716:
713:
709:
705:
701:
697:
693:
690:
687:
683:
680:
676:
673:
672:
671:
669:
665:
660:
658:
654:
650:
646:
642:
639: =
638:
634:
630:
626:
622:
618:
614:
610:
606:
602:
598:
594:
590:
586:
582:
557:
546:
515:
504:
501:
498:
495:
492:
469:
447:
443:
414:
403:
400:
397:
377:
369:
350:
347:
344:
341:
338:
327:
323:
307:
300:
296:
286:
284:
281: =
280:
276:
272:
269: =
268:
264:
260:
256:
252:
249: =
248:
244:
239:
237:
234: =
233:
229:
225:
222: =
221:
217:
213:
210: =
209:
205:
201:
198: =
197:
193:
188:
186:
183: ≠
182:
177:
176:
170:
168:
164:
160:
156:
152:
149: =
148:
144:
140:
130:
128:
124:
121: ≠
120:
116:
112:
108:
104:
101: ≠
100:
96:
92:
88:
84:
83:
78:
74:
69:
63:
60:
59:
58:
56:
51:
49:
45:
41:
37:
36:
31:
27:
23:
19:
1108:
988:
978:
963:
937:
933:
923:
909:
905:
885:
884:
879:
875:
871:
861:
856:
852:
848:
846:
811:
809:
789:
785:
773:
769:
765:
761:
751:
747:
732:
729:Horn clauses
711:
707:
706:, is vertex
703:
699:
667:
663:
661:
656:
652:
648:
644:
640:
636:
635:ones, where
632:
628:
624:
620:
616:
608:
604:
600:
596:
592:
584:
580:
367:
324:(written in
321:
294:
292:
282:
278:
274:
270:
266:
262:
258:
254:
250:
246:
242:
240:
235:
231:
227:
223:
219:
215:
211:
207:
203:
199:
195:
189:
184:
180:
173:
171:
166:
162:
158:
154:
150:
146:
142:
138:
136:
126:
122:
118:
110:
102:
98:
94:
90:
80:
76:
72:
70:
67:
54:
52:
43:
39:
34:
25:
15:
1229:#P-complete
1167:NP-complete
1082:NL-complete
898:linear time
192:NP-complete
1284:ELEMENTARY
1109:P-complete
957:References
864:Jin-Yi Cai
137:The class
133:Motivation
55:P-complete
26:P-complete
1279:2-EXPTIME
862:In 1999,
597:much more
527:⟩
490:⟨
462:deciding
354:⟩
336:⟨
1405:Category
1274:EXPSPACE
1269:NEXPTIME
1037:DLOGTIME
870:that is
30:complete
1264:EXPTIME
1172:NP-hard
800:untyped
679:circuit
48:reduced
46:can be
1371:NSPACE
1366:DSPACE
1241:PSPACE
970:
754:steps?
613:binary
1361:NTIME
1356:DTIME
1177:co-NP
916:Notes
900:by a
696:graph
685:layer
326:unary
20:, a
1189:TFNP
968:ISBN
792:?".)
782:gzip
778:LZ77
764:and
702:and
1304:ALL
1204:QMA
1194:FNP
1136:APX
1131:BQP
1126:BPP
1116:ZPP
1047:ACC
942:doi
851:is
788:in
328:),
24:is
16:In
1407::
1299:RE
1289:PR
1236:IP
1224:#P
1219:PP
1214:⊕P
1209:PH
1199:AM
1162:NP
1157:UP
1141:FP
1121:RP
1099:CC
1094:SC
1089:NC
1077:NL
1072:FL
1067:RL
1062:SL
1052:TC
1042:AC
966:.
938:58
936:,
932:,
882:.
733:P'
657:NC
581:NC
482:,
285:.
267:NC
263:NC
255:NC
251:NP
243:NP
238:.
220:NC
208:NC
200:NP
169:.
163:NC
159:NP
147:NC
143:NC
99:NC
95:NC
82:NC
1294:R
1104:P
1057:L
1015:e
1008:t
1001:v
944::
910:P
906:P
886:P
880:P
876:L
872:P
857:P
853:P
849:P
830:0
826:C
822:A
812:P
790:s
786:t
774:t
770:s
766:t
762:s
752:T
748:T
739:.
712:v
708:u
704:v
700:u
668:P
664:P
653:P
649:T
645:n
641:T
637:n
633:n
629:T
625:T
621:n
617:n
609:T
605:T
601:P
593:P
585:P
566:)
562:|
558:x
554:|
550:(
547:p
524:)
520:|
516:x
512:|
508:(
505:p
502:,
499:x
496:,
493:M
470:L
448:L
444:M
423:)
419:|
415:x
411:|
407:(
404:p
401:=
398:T
378:L
368:T
351:T
348:,
345:x
342:,
339:M
322:T
308:M
295:P
283:P
279:L
275:P
271:P
259:P
247:P
236:P
232:L
228:P
224:P
216:P
212:P
204:P
196:P
185:P
181:L
175:L
167:P
155:P
151:P
139:P
127:P
123:P
119:L
115:L
111:P
103:P
91:P
77:P
73:P
44:P
40:P
35:P
28:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.