44:
in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure
493:: Given a list of pairs of strings, determine if there is a selection from these pairs (allowing repeats) such that the concatenation of the first items (of the pairs) is equal to the concatenation of the second items.
342:
210:. In fact, it is the intersection of those two classes, because we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result. Therefore:
183:
on every input and outputting strings that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps).
255:
273:. These are the set of languages for which neither membership nor non-membership can be proven in a finite amount of time, and contain all other languages that are not in either
181:
161:
141:
121:
88:
is the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means). Each member of
392:. In a sense, these are the "hardest" recursively enumerable problems. Generally, no constraint is placed on the reductions used except that they must be
287:
644:
if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.
790:
163:
accepts when an input is in a language, another machine can enumerate all strings in the language by interleaving simulations of
216:
76:
contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever.
552:
1152:
783:
21:
1192:
572:
557:
348:
Not only are these problems undecidable, but neither they nor their complement are recursively enumerable.
1187:
776:
638:(if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an
490:
1168:
975:
443:
93:
29:
365:
359:(the class where a classical verifier interacts with multiple all-powerful quantum provers who share
1157:
370:
455:
65:
1111:
617:
374:
673:
Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE".
1106:
1101:
562:
694:
Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (November 2021).
1096:
759:
497:
466:
360:
17:
8:
447:
414:
516:. In a sense, these are the complements of the hardest recursively enumerable problems.
717:
674:
610:
393:
193:
166:
146:
126:
106:
1116:
721:
539:
484:
410:
123:
that enumerates all accepted inputs, another machine that takes in a string can run
1080:
970:
902:
892:
799:
747:
707:
480:
37:
33:
661:
1065:
1022:
1012:
1005:
995:
985:
943:
938:
933:
917:
897:
875:
870:
865:
853:
848:
843:
838:
755:
567:
403:
97:
612:
Logic and
Algorithms, With Applications to the Computer and Information Sciences
596:
1070:
958:
880:
833:
656:
591:
535:
524:
469:
198:
41:
406:: Whether a program given a finite input finishes running or will run forever.
1181:
751:
46:
432:
337:{\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}
948:
858:
735:
424:
1060:
885:
421:-hard. It will be complete whenever the set is recursively enumerable.
1055:
768:
640:
528:
451:
54:
712:
695:
1050:
1045:
990:
813:
679:
1040:
740:
Zeitschrift für
Mathematische Logik und Grundlagen der Mathematik
363:); a revised, but not yet fully reviewed, proof was published in
143:
and accept if the string is enumerated. Conversely, if a machine
1147:
1142:
1017:
1000:
49:" for some 'no' cases. Such a procedure is sometimes called a
1137:
1132:
953:
413:, deciding membership in any nontrivial subset of the set of
103:
To show this is equivalent, note that if there is a machine
965:
823:
980:
912:
907:
828:
818:
250:{\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}
57:, defined as a complete solution to a decision problem.
693:
672:
512:
is the set of decision problems that are complete for
388:
is the set of decision problems that are complete for
351:
In
January of 2020, a preprint announced a proof that
325:
315:
302:
292:
241:
231:
221:
290:
219:
169:
149:
129:
109:
609:
336:
261:Conversely, the set of languages that are neither
249:
175:
155:
135:
115:
1179:
40:for which a 'yes' answer can be verified by a
784:
369:in November 2021. The proof implies that the
187:
45:is not required to halt; it may go into an "
472:. (Again, certain individual grammars have
791:
777:
711:
678:
607:
79:
456:word problem for some individual groups
1180:
798:
734:
622:A method of solution will be called a
519:Examples of co-RE-complete problems:
428:
772:
64:is the set of all languages that are
13:
399:Examples of RE-complete problems:
14:
1204:
1153:Probabilistically checkable proof
553:Knuth–Bendix completion algorithm
504:
465:Deciding membership in a general
476:-complete membership problems.)
22:computational complexity theory
728:
687:
666:
649:
601:
584:
380:
331:
311:
1:
578:
608:Korfhage, Robert R. (1966).
558:List of undecidable problems
355:was equivalent to the class
53:, to distinguish it from an
7:
546:
491:Post correspondence problem
10:
1209:
1169:List of complexity classes
500:has any integer solutions.
188:Relations to other classes
94:recursively enumerable set
1166:
1125:
1089:
1033:
926:
806:
738:(1955), "Creative sets",
700:Communications of the ACM
366:Communications of the ACM
1158:Interactive proof system
752:10.1002/malq.19550010205
371:Connes embedding problem
1112:Arithmetical hierarchy
338:
251:
202:) is a subset of both
177:
157:
137:
117:
30:recursively enumerable
1107:Grzegorczyk hierarchy
1102:Exponential hierarchy
1034:Considered infeasible
563:Polymorphic recursion
339:
252:
178:
158:
138:
118:
80:Equivalent definition
1193:Undecidable problems
1097:Polynomial hierarchy
927:Suspected infeasible
498:Diophantine equation
288:
217:
167:
147:
127:
107:
18:computability theory
1126:Families of classes
807:Considered feasible
634:if the solution to
415:recursive functions
394:many-one reductions
375:Tsirelson's problem
194:recursive languages
1188:Complexity classes
800:Complexity classes
431:) proved that all
334:
329:
319:
306:
296:
247:
245:
235:
225:
173:
153:
133:
113:
1175:
1174:
1117:Boolean hierarchy
1090:Class hierarchies
616:. Wiley. p.
540:first-order logic
496:Determining if a
485:first-order logic
328:
318:
305:
295:
244:
234:
224:
176:{\displaystyle M}
156:{\displaystyle M}
136:{\displaystyle E}
116:{\displaystyle E}
68:of a language in
38:decision problems
1200:
793:
786:
779:
770:
769:
764:
762:
732:
726:
725:
715:
691:
685:
684:
682:
670:
664:
653:
647:
646:
615:
605:
599:
588:
573:Semidecidability
343:
341:
340:
335:
330:
326:
320:
316:
307:
303:
297:
293:
256:
254:
253:
248:
246:
242:
236:
232:
226:
222:
182:
180:
179:
174:
162:
160:
159:
154:
142:
140:
139:
134:
122:
120:
119:
114:
96:and therefore a
1208:
1207:
1203:
1202:
1201:
1199:
1198:
1197:
1178:
1177:
1176:
1171:
1162:
1121:
1085:
1029:
1023:PSPACE-complete
922:
802:
797:
767:
733:
729:
713:10.1145/3485628
706:(11): 131–138.
692:
688:
671:
667:
654:
650:
606:
602:
589:
585:
581:
568:Risch algorithm
549:
507:
454:. (Indeed, the
425:John Myhill
404:Halting problem
383:
324:
314:
301:
291:
289:
286:
285:
240:
230:
220:
218:
215:
214:
190:
168:
165:
164:
148:
145:
144:
128:
125:
124:
108:
105:
104:
98:Diophantine set
82:
72:. In a sense,
12:
11:
5:
1206:
1196:
1195:
1190:
1173:
1172:
1167:
1164:
1163:
1161:
1160:
1155:
1150:
1145:
1140:
1135:
1129:
1127:
1123:
1122:
1120:
1119:
1114:
1109:
1104:
1099:
1093:
1091:
1087:
1086:
1084:
1083:
1078:
1073:
1068:
1063:
1058:
1053:
1048:
1043:
1037:
1035:
1031:
1030:
1028:
1027:
1026:
1025:
1015:
1010:
1009:
1008:
998:
993:
988:
983:
978:
973:
968:
963:
962:
961:
959:co-NP-complete
956:
951:
946:
936:
930:
928:
924:
923:
921:
920:
915:
910:
905:
900:
895:
890:
889:
888:
878:
873:
868:
863:
862:
861:
851:
846:
841:
836:
831:
826:
821:
816:
810:
808:
804:
803:
796:
795:
788:
781:
773:
766:
765:
727:
686:
665:
657:Complexity Zoo
648:
624:semi-algorithm
600:
592:Complexity Zoo
582:
580:
577:
576:
575:
570:
565:
560:
555:
548:
545:
544:
543:
536:satisfiability
532:
525:domino problem
510:co-RE-complete
506:
505:co-RE-complete
503:
502:
501:
494:
488:
477:
470:formal grammar
463:
440:
422:
411:Rice's Theorem
407:
382:
379:
346:
345:
333:
323:
313:
310:
300:
259:
258:
239:
229:
189:
186:
172:
152:
132:
112:
84:Equivalently,
81:
78:
51:semi-algorithm
42:Turing machine
9:
6:
4:
3:
2:
1205:
1194:
1191:
1189:
1186:
1185:
1183:
1170:
1165:
1159:
1156:
1154:
1151:
1149:
1146:
1144:
1141:
1139:
1136:
1134:
1131:
1130:
1128:
1124:
1118:
1115:
1113:
1110:
1108:
1105:
1103:
1100:
1098:
1095:
1094:
1092:
1088:
1082:
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1057:
1054:
1052:
1049:
1047:
1044:
1042:
1039:
1038:
1036:
1032:
1024:
1021:
1020:
1019:
1016:
1014:
1011:
1007:
1004:
1003:
1002:
999:
997:
994:
992:
989:
987:
984:
982:
979:
977:
974:
972:
969:
967:
964:
960:
957:
955:
952:
950:
947:
945:
942:
941:
940:
937:
935:
932:
931:
929:
925:
919:
916:
914:
911:
909:
906:
904:
901:
899:
896:
894:
891:
887:
884:
883:
882:
879:
877:
874:
872:
869:
867:
864:
860:
857:
856:
855:
852:
850:
847:
845:
842:
840:
837:
835:
832:
830:
827:
825:
822:
820:
817:
815:
812:
811:
809:
805:
801:
794:
789:
787:
782:
780:
775:
774:
771:
761:
757:
753:
749:
746:(2): 97–108,
745:
741:
737:
731:
723:
719:
714:
709:
705:
701:
697:
690:
681:
676:
669:
663:
659:
658:
652:
645:
643:
642:
637:
633:
629:
625:
619:
614:
613:
604:
598:
594:
593:
587:
583:
574:
571:
569:
566:
564:
561:
559:
556:
554:
551:
550:
541:
537:
533:
530:
526:
522:
521:
520:
517:
515:
511:
499:
495:
492:
489:
486:
482:
478:
475:
471:
468:
464:
461:
457:
453:
449:
445:
441:
438:
434:
433:creative sets
430:
426:
423:
420:
416:
412:
408:
405:
402:
401:
400:
397:
395:
391:
387:
378:
376:
372:
368:
367:
362:
358:
354:
349:
321:
308:
298:
284:
283:
282:
280:
276:
272:
268:
264:
237:
227:
213:
212:
211:
209:
205:
201:
200:
195:
185:
170:
150:
130:
110:
101:
99:
95:
91:
87:
77:
75:
71:
67:
63:
58:
56:
52:
48:
47:infinite loop
43:
39:
35:
31:
27:
23:
19:
1075:
743:
739:
736:Myhill, John
730:
703:
699:
689:
668:
655:
651:
639:
635:
631:
627:
623:
621:
611:
603:
590:
586:
538:problem for
518:
513:
509:
508:
483:problem for
473:
467:unrestricted
459:
444:word problem
442:The uniform
436:
418:
398:
389:
385:
384:
364:
361:entanglement
356:
352:
350:
347:
278:
274:
270:
269:is known as
266:
262:
260:
207:
203:
197:
191:
102:
89:
85:
83:
73:
69:
61:
59:
50:
25:
15:
1006:#P-complete
944:NP-complete
859:NL-complete
696:"MIP* = RE"
662:Class co-RE
462:-complete.)
386:RE-complete
381:RE-complete
377:are false.
281:. That is:
192:The set of
66:complements
60:Similarly,
1182:Categories
1061:ELEMENTARY
886:P-complete
680:2001.04383
579:References
529:Wang tiles
452:semigroups
439:-complete.
1056:2-EXPTIME
722:210165045
641:algorithm
322:∪
309:−
238:∩
55:algorithm
32:) is the
1051:EXPSPACE
1046:NEXPTIME
814:DLOGTIME
597:Class RE
547:See also
481:validity
1041:EXPTIME
949:NP-hard
760:0071379
427: (
1148:NSPACE
1143:DSPACE
1018:PSPACE
758:
720:
448:groups
1138:NTIME
1133:DTIME
954:co-NP
718:S2CID
675:arXiv
626:for
514:co-RE
327:co-RE
279:co-RE
267:co-RE
243:co-RE
208:co-RE
92:is a
74:co-RE
62:co-RE
34:class
966:TFNP
630:on
534:The
527:for
523:The
479:The
446:for
435:are
429:1955
373:and
357:MIP*
294:NRNC
271:NRNC
265:nor
206:and
20:and
1081:ALL
981:QMA
971:FNP
913:APX
908:BQP
903:BPP
893:ZPP
824:ACC
748:doi
708:doi
458:is
450:or
417:is
409:By
353:RE
304:ALL
277:or
36:of
16:In
1184::
1076:RE
1066:PR
1013:IP
1001:#P
996:PP
991:⊕P
986:PH
976:AM
939:NP
934:UP
918:FP
898:RP
876:CC
871:SC
866:NC
854:NL
849:FL
844:RL
839:SL
829:TC
819:AC
756:MR
754:,
742:,
716:.
704:64
702:.
698:.
660::
620:.
618:89
595::
474:RE
460:RE
437:RE
419:RE
396:.
390:RE
317:RE
275:RE
263:RE
233:RE
204:RE
100:.
90:RE
86:RE
70:RE
26:RE
24:,
1071:R
881:P
834:L
792:e
785:t
778:v
763:.
750::
744:1
724:.
710::
683:.
677::
636:P
632:M
628:P
542:.
531:.
487:.
344:.
332:)
312:(
299:=
257:.
228:=
223:R
199:R
196:(
171:M
151:M
131:E
111:E
28:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.