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