377:, several equivalent problems of converting logical formulas between conjunctive and disjunctive normal form, listing all minimal hitting sets of a family of sets, or listing all minimal set covers of a family of sets, with time complexity measured in the combined input and output size.
311:
170:
212:
1127:
98:
72:
715:
383:, involving token-passing along the edges of a colored directed graph. The paper giving a quasi-polynomial algorithm for these games won the 2021
322:
813:
Calude, Cristian S.; Jain, Sanjay; Khoussainov, Bakhadyr; Li, Wei; Stephan, Frank (2022), "Deciding parity games in quasi-polynomial time",
676:
109:
421:, determining whether two graphs can be made equal to each other by relabeling their vertices, announced in 2015 and updated in 2017 by
1178:
1173:
1051:
890:
935:
626:
Proceedings of the 31st Annual ACM–SIAM Symposium on
Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020
652:
462:
17:
1136:
Proceedings of the 26th Annual ACM–SIAM Symposium on
Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4–6, 2015
1059:
775:
Eiter, Thomas; Makino, Kazuhisa; Gottlob, Georg (2008), "Computational aspects of monotone dualization: a brief survey",
1054:; Rzazewski, Pawel; Sikora, Florian (2018), "QPTAS and subexponential algorithm for maximum clique on disk graphs", in
391:
341:
1134:
624:
1163:
35:
1084:
671:
777:
466:
1168:
413:
Problems for which a quasi-polynomial time algorithm has been announced but not fully published include:
337:
306:{\displaystyle {\mathsf {QP}}=\bigcup _{c\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{(\log n)^{c}}\right)}
973:
409:, a subset of the vertices of the tournament that has at least one directed edge to all other vertices.
1061:
34th
International Symposium on Computational Geometry, SoCG 2018, June 11–14, 2018, Budapest, Hungary
815:
731:
729:
Hazan, Elad; Krauthgamer, Robert (2011), "How hard is it to approximate the best Nash equilibrium?",
577:
418:
406:
745:
202:
consists of all problems that have quasi-polynomial time algorithms. It can be defined in terms of
454:
51:
1064:, LIPIcs, vol. 99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 12:1–12:15,
1090:
881:
740:
619:
Kisfaludi-Bak, Sándor (2020), "Hyperbolic intersection graphs and (quasi)-polynomial time", in
39:
28:
994:
Marc
Lackenby announces a new unknot recognition algorithm that runs in quasi-polynomial time
585:
531:
465:
whose running time is quasi-polynomial rather than polynomial. Problems with a QPTAS include
998:
956:
913:
846:
800:
762:
374:
8:
1022:(2009), "A quasi-polynomial time approximation scheme for minimum weight triangulation",
75:
344:. For instance, this is true for finding the largest disjoint subset of a collection of
1024:
885:
685:
630:
602:
548:
474:
429:
359:
Other problems for which the best known algorithm takes quasi-polynomial time include:
330:
83:
57:
1087:; Kun-Ko, Young; Weinstein, Omri (2015), "Approximating the best Nash equilibrium in
1055:
948:
709:
648:
422:
1140:
1065:
1033:
944:
899:
832:
824:
786:
750:
695:
640:
594:
565:
540:
481:
353:
349:
175:
336:
In some cases, quasi-polynomial time bounds can be proven to be optimal under the
1019:
978:
969:
952:
909:
842:
796:
758:
518:
179:
47:
1070:
644:
598:
506:
371:
has been modified by adding edges between all pairs of a subset of its vertices.
1144:
926:
667:
522:
501:
470:
402:
395:
364:
183:
791:
352:, and for finding a graph with the fewest vertices that does not appear as an
1157:
888:(1996), "On limited nondeterminism and the complexity of the V-C dimension",
620:
526:
441:
1037:
904:
859:
573:
569:
484:
has a QPTAS, but cannot have a PTAS under the exponential time hypothesis.
433:
384:
368:
326:
1130:
930:
380:
103:
992:
828:
700:
674:(2023), "Quasipolynomiality of the smallest missing induced subgraph",
606:
552:
178:
with quasi-polynomial time algorithms are natural candidates for being
837:
754:
345:
329:
has subsequently been shown to have a polynomial time algorithm, the
544:
690:
635:
529:(1983), "On distinguishing prime numbers from composite numbers",
187:
933:(1988), "On finding a minimum dominating set in a tournament",
437:
1049:
321:
An early example of a quasi-polynomial time algorithm was the
203:
1083:
325:; however, the problem of testing whether a number is a
880:
812:
666:
1093:
517:
480:
More strongly, the problem of finding an approximate
215:
112:
86:
60:
165:{\displaystyle 2^{O{\bigl (}(\log n)^{c}{\bigr )}}.}
1129:-time breaks the Exponential Time Hypothesis", in
1121:
774:
564:
453:Quasi-polynomial time has also been used to study
305:
164:
92:
66:
1155:
728:
925:
448:
618:
152:
123:
714:: CS1 maint: DOI inactive as of July 2024 (
677:Journal of Graph Algorithms and Applications
1043:
1017:
459:quasi-polynomial-time approximation scheme
1069:
968:
903:
836:
790:
744:
699:
689:
634:
241:
54:. That is, there should exist a constant
962:
919:
891:Journal of Computer and System Sciences
612:
323:Adleman–Pomerance–Rumely primality test
14:
1156:
1050:Bonnet, Édouard; Giannopoulos, Panos;
985:
974:"Graph isomorphism vanquished — again"
768:
722:
660:
261:
258:
255:
252:
249:
221:
218:
874:
852:
806:
1077:
463:polynomial-time approximation scheme
1011:
193:
24:
558:
511:
494:
367:problem, of determining whether a
25:
1190:
342:computational hardness assumption
1179:Quasi-polynomial time algorithms
1174:Computational complexity theory
78:of the algorithm, on inputs of
42:, an algorithm is said to take
36:computational complexity theory
1114:
1102:
672:Williams, Virginia Vassilevska
507:Class QP: Quasipolynomial-Time
288:
275:
141:
128:
13:
1:
487:
392:Vapnik–Chervonenkis dimension
949:10.1016/0304-3975(88)90131-4
936:Theoretical Computer Science
823:(2): STOC17-152–STOC17-188,
778:Discrete Applied Mathematics
467:minimum-weight triangulation
7:
1071:10.4230/LIPICS.SOCG.2018.12
645:10.1137/1.9781611975994.100
599:10.4007/annals.2004.160.781
449:In approximation algorithms
338:exponential time hypothesis
316:
10:
1195:
1145:10.1137/1.9781611973730.66
1122:{\textstyle n^{o(\log n)}}
997:, Mathematical Institute,
882:Papadimitriou, Christos H.
461:(QPTAS) is a variant of a
52:quasi-polynomially bounded
26:
1058:; TĂłth, Csaba D. (eds.),
816:SIAM Journal on Computing
792:10.1016/j.dam.2007.04.017
732:SIAM Journal on Computing
419:graph isomorphism problem
455:approximation algorithms
432:, recognizing whether a
27:Not to be confused with
1038:10.1145/1516512.1516517
76:worst-case running time
1164:Analysis of algorithms
1123:
905:10.1006/jcss.1996.0058
629:, pp. 1621–1638,
307:
166:
94:
68:
40:analysis of algorithms
29:Pseudo-polynomial time
1124:
704:(inactive 2024-07-29)
586:Annals of Mathematics
532:Annals of Mathematics
401:Finding the smallest
308:
198:The complexity class
167:
95:
69:
44:quasi-polynomial time
1139:, pp. 970–982,
1091:
999:University of Oxford
972:(January 14, 2017),
375:Monotone dualization
213:
110:
84:
58:
18:Quasipolynomial time
886:Yannakakis, Mihalis
670:; Lincoln, Andrea;
519:Adleman, Leonard M.
457:. In particular, a
1169:Complexity classes
1119:
1056:Speckmann, Bettina
1032:(3), Article A15,
1025:Journal of the ACM
829:10.1137/17M1145288
701:10.7155/jgaa.00625
475:intersection graph
469:, and finding the
430:unknotting problem
356:of a given graph.
331:AKS primality test
303:
246:
162:
90:
64:
861:IPEC Nerode Prize
785:(11): 2035–2049,
755:10.1137/090766991
654:978-1-61197-599-4
566:Agrawal, Manindra
527:Rumely, Robert S.
229:
186:nor likely to be
182:, neither having
176:decision problems
93:{\displaystyle n}
67:{\displaystyle c}
16:(Redirected from
1186:
1148:
1147:
1128:
1126:
1125:
1120:
1118:
1117:
1081:
1075:
1074:
1073:
1047:
1041:
1040:
1020:Steger, Angelika
1015:
1009:
1008:
1007:
1006:
989:
983:
982:
970:Klarreich, Erica
966:
960:
959:
943:(2–3): 307–316,
923:
917:
916:
907:
878:
872:
871:
870:
869:
856:
850:
849:
840:
810:
804:
803:
794:
772:
766:
765:
748:
726:
720:
719:
713:
705:
703:
693:
664:
658:
657:
638:
616:
610:
609:
582:
578:"PRIMES is in P"
562:
556:
555:
515:
509:
498:
482:Nash equilibrium
354:induced subgraph
350:hyperbolic plane
312:
310:
309:
304:
302:
298:
297:
296:
295:
265:
264:
245:
244:
225:
224:
194:Complexity class
171:
169:
168:
163:
158:
157:
156:
155:
149:
148:
127:
126:
101:
99:
97:
96:
91:
73:
71:
70:
65:
21:
1194:
1193:
1189:
1188:
1187:
1185:
1184:
1183:
1154:
1153:
1152:
1151:
1098:
1094:
1092:
1089:
1088:
1085:Braverman, Mark
1082:
1078:
1048:
1044:
1016:
1012:
1004:
1002:
991:
990:
986:
979:Quanta Magazine
967:
963:
927:Megiddo, Nimrod
924:
920:
879:
875:
867:
865:
858:
857:
853:
811:
807:
773:
769:
746:10.1.1.511.4422
727:
723:
707:
706:
668:Eppstein, David
665:
661:
655:
617:
613:
580:
563:
559:
545:10.2307/2006975
523:Pomerance, Carl
516:
512:
499:
495:
490:
451:
440:, announced by
319:
291:
287:
274:
270:
266:
248:
247:
240:
233:
217:
216:
214:
211:
210:
196:
184:polynomial time
180:NP-intermediate
151:
150:
144:
140:
122:
121:
117:
113:
111:
108:
107:
85:
82:
81:
79:
59:
56:
55:
48:time complexity
32:
23:
22:
15:
12:
11:
5:
1192:
1182:
1181:
1176:
1171:
1166:
1150:
1149:
1116:
1113:
1110:
1107:
1104:
1101:
1097:
1076:
1042:
1010:
984:
961:
918:
898:(2): 161–170,
873:
851:
805:
767:
721:
684:(5): 329–339,
659:
653:
621:Chawla, Shuchi
611:
593:(2): 781–793,
557:
539:(1): 173–206,
510:
502:Complexity Zoo
492:
491:
489:
486:
471:maximum clique
450:
447:
446:
445:
436:describes the
426:
411:
410:
403:dominating set
399:
396:family of sets
390:Computing the
388:
378:
372:
365:planted clique
318:
315:
314:
313:
301:
294:
290:
286:
283:
280:
277:
273:
269:
263:
260:
257:
254:
251:
243:
239:
236:
232:
228:
223:
220:
195:
192:
161:
154:
147:
143:
139:
136:
133:
130:
125:
120:
116:
89:
74:such that the
63:
9:
6:
4:
3:
2:
1191:
1180:
1177:
1175:
1172:
1170:
1167:
1165:
1162:
1161:
1159:
1146:
1142:
1138:
1137:
1132:
1111:
1108:
1105:
1099:
1095:
1086:
1080:
1072:
1067:
1063:
1062:
1057:
1053:
1052:Kim, Eun Jung
1046:
1039:
1035:
1031:
1027:
1026:
1021:
1014:
1000:
996:
995:
988:
981:
980:
975:
971:
965:
958:
954:
950:
946:
942:
938:
937:
932:
928:
922:
915:
911:
906:
901:
897:
893:
892:
887:
883:
877:
863:
862:
855:
848:
844:
839:
834:
830:
826:
822:
818:
817:
809:
802:
798:
793:
788:
784:
780:
779:
771:
764:
760:
756:
752:
747:
742:
738:
734:
733:
725:
717:
711:
702:
697:
692:
687:
683:
679:
678:
673:
669:
663:
656:
650:
646:
642:
637:
632:
628:
627:
622:
615:
608:
604:
600:
596:
592:
588:
587:
579:
575:
574:Saxena, Nitin
571:
570:Kayal, Neeraj
567:
561:
554:
550:
546:
542:
538:
534:
533:
528:
524:
520:
514:
508:
504:
503:
497:
493:
485:
483:
478:
476:
472:
468:
464:
460:
456:
443:
442:Marc Lackenby
439:
435:
431:
427:
424:
420:
416:
415:
414:
408:
404:
400:
397:
393:
389:
386:
382:
379:
376:
373:
370:
366:
362:
361:
360:
357:
355:
351:
347:
343:
340:or a related
339:
334:
332:
328:
324:
299:
292:
284:
281:
278:
271:
267:
237:
234:
230:
226:
209:
208:
207:
205:
201:
191:
189:
185:
181:
177:
172:
159:
145:
137:
134:
131:
118:
114:
105:
87:
77:
61:
53:
49:
45:
41:
37:
30:
19:
1135:
1131:Indyk, Piotr
1079:
1060:
1045:
1029:
1023:
1013:
1003:, retrieved
1001:, 2021-02-03
993:
987:
977:
964:
940:
934:
931:Vishkin, Uzi
921:
895:
889:
876:
866:, retrieved
860:
854:
820:
814:
808:
782:
776:
770:
739:(1): 79–91,
736:
730:
724:
681:
675:
662:
625:
614:
590:
584:
560:
536:
530:
513:
500:
496:
479:
458:
452:
434:knot diagram
423:László Babai
412:
385:Nerode Prize
381:Parity games
369:random graph
358:
335:
327:prime number
320:
206:as follows.
199:
197:
173:
106:of the form
43:
33:
1018:Remy, Jan;
104:upper bound
1158:Categories
1005:2021-02-03
868:2023-12-03
838:2292/31757
691:2306.11185
636:1812.03960
488:References
477:of disks.
407:tournament
346:unit disks
1109:
741:CiteSeerX
282:
238:∈
231:⋃
135:
710:citation
576:(2004),
444:in 2021.
317:Examples
38:and the
1133:(ed.),
957:0980249
914:1418886
864:, EATCS
847:4413072
801:2437000
763:2765712
623:(ed.),
607:3597229
553:2006975
473:on the
348:in the
188:NP-hard
102:has an
46:if its
955:
912:
845:
799:
761:
743:
651:
605:
551:
438:unknot
686:arXiv
631:arXiv
603:JSTOR
581:(PDF)
549:JSTOR
405:in a
394:of a
204:DTIME
80:size
716:link
649:ISBN
428:The
417:The
363:The
174:The
1141:doi
1106:log
1066:doi
1034:doi
945:doi
900:doi
833:hdl
825:doi
787:doi
783:156
751:doi
696:doi
641:doi
595:doi
591:160
541:doi
537:117
279:log
132:log
50:is
34:In
1160::
1030:56
1028:,
976:,
953:MR
951:,
941:61
939:,
929:;
910:MR
908:,
896:53
894:,
884:;
843:MR
841:,
831:,
821:51
819:,
797:MR
795:,
781:,
759:MR
757:,
749:,
737:40
735:,
712:}}
708:{{
694:,
682:27
680:,
647:,
639:,
601:,
589:,
583:,
572:;
568:;
547:,
535:,
525:;
521:;
505::
333:.
200:QP
190:.
1143::
1115:)
1112:n
1103:(
1100:o
1096:n
1068::
1036::
947::
902::
835::
827::
789::
753::
718:)
698::
688::
643::
633::
597::
543::
425:.
398:.
387:.
300:)
293:c
289:)
285:n
276:(
272:2
268:(
262:E
259:M
256:I
253:T
250:D
242:N
235:c
227:=
222:P
219:Q
160:.
153:)
146:c
142:)
138:n
129:(
124:(
119:O
115:2
100:,
88:n
62:c
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.