1702:
formulas in which each variable appears only a constant number of times, and therefore in which the number of clauses is linear. The sparsification lemma is proven by repeatedly finding large sets of clauses that have a nonempty common intersection in a given formula, and replacing the formula by two
3040:
are specified, and three communicating parties each know two of the three subsets. The goal is for the parties to transmit as few bits to each other on a shared communications channel in order for one of the parties to be able to determine whether the intersection of the three sets is empty or
2222:
If cliques or independent sets of logarithmic size could be found in polynomial time, the exponential time hypothesis would be false. Therefore, even though finding cliques or independent sets of such small size is unlikely to be NP-complete, the exponential time hypothesis implies that these
1703:
simpler formulas, one of which has each of these clauses replaced by their common intersection and the other of which has the intersection removed from each clause. By applying the sparsification lemma and then using new variables to split the clauses, one may then obtain a set of
156:, but it is a stronger statement. It implies that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do, and that many known algorithms for these problems have optimal or near-optimal time
3226:
violating the strong exponential time hypothesis. Therefore, the strong exponential time hypothesis implies either that the trivial protocol for three-party set disjointness is optimal, or that any better protocol requires an exponential amount of
3068:
describing the intersection of the two sets known to that party, after which either of the two remaining parties can determine the emptiness of the intersection. However, if there exists a protocol that solves the problem with
3436:
3322:
and if the best possible running time for 3-SAT were of this form, then P would be unequal to NP (because 3-SAT is NP-complete and this time bound is not polynomial) but the exponential time hypothesis would be false.
1048:
tending towards zero, but where the descriptions of these algorithms are so quickly growing that a single algorithm could not automatically select and run the most appropriate one. If this were to be the case, then
822:
2593:
2521:
379:
1273:
3577:
1493:
2970:
2869:
2787:
2704:
3326:
In parameterized complexity theory, because the exponential time hypothesis implies that there does not exist a fixed-parameter-tractable algorithm for maximum clique, it also implies that
1765:
formula is satisfiable if and only if at least one of these 3-CNF formulas is satisfiable. Therefore, if 3-SAT could be solved in subexponential time, one could use this reduction to solve
745:
2101:
2003:
1974:
3611:
It is also possible to prove implications in the other direction, from the failure of a variation of the strong exponential time hypothesis to separations of complexity classes. As
1740:
1677:
3938:
Chen, Yijia; Eickmeyer, Kord; Flum, Jörg (2012), "The exponential time hypothesis and the parameterized clique problem", in
Thilikos, Dimitrios M.; Woeginger, Gerhard J. (eds.),
1019:
1210:
1613:
3337:
imply the exponential time hypothesis? There is a hierarchy of parameterized complexity classes called the M-hierarchy that interleaves the W-hierarchy in the sense that, for
2064:
676:
559:
1312:
4502:
3199:
1918:
1380:
1046:
150:
3677:
2439:
1885:
1821:
110:
3291:
3136:
2370:
2283:
1160:
1112:
944:
904:
563:
This minimum might not exist, if a sequence of better and better algorithms have correspondingly smaller exponential growth in their time bounds; in that case, define
77:
3471:
2023:
1577:
1428:
612:
453:
3603:
3318:
1850:
2143:
1945:
1542:
1353:
1074:
973:
858:
588:
482:
3097:
2068:
Therefore, if the strong exponential time hypothesis is true, then there would be no algorithm for general CNF satisfiability that is significantly faster than a
3875:
3773:
3749:
3729:
3699:
3633:
3516:
3492:
3357:
3222:
3159:
3060:
2892:
2627:
2393:
2332:
2312:
2245:
2212:
2165:
1784:
1761:
1698:
1636:
1515:
1402:
698:
633:
503:
420:
399:
305:
280:
256:
228:
186:
3037:
3246:
algorithm, so NP could not be a subset of QP. However, if the exponential time hypothesis fails, it would have no implication for the P versus NP problem. A
752:
230:
variables per clause. The goal is to determine whether this expression can be made to be true by some assignment of
Boolean values to its variables.
4495:
3364:
3976:
Parameterized and Exact
Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers
312:
4278:
Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015),
975:
would equal zero. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time
1219:
2607:. In particular, if the strong exponential time hypothesis is true, then the optimal time bound for finding independent sets on graphs of
4705:
4586:
4550:
4488:
2216:
graphs. Conversely, if any of these problems has a subexponential algorithm, then the exponential time hypothesis could be shown to be
3238:
If the exponential time hypothesis is true, then 3-SAT would not have a polynomial time algorithm, and therefore it would follow that
3940:
Parameterized and Exact
Computation – 7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12–14, 2012, Proceedings
4581:
4132:
4224:; Schudy, Warren (2010), "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament",
3751:
could be composed with the circuits to simulate NEXPTIME problems nondeterministically in a smaller amount of time, violating the
2530:
2458:
4302:
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), "Known algorithms on graphs of bounded treewidth are probably optimal",
4193:
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity",
4471:
4287:
4255:
4090:
3923:
3834:
4059:
2227:
More generally, the exponential time hypothesis implies that it is not possible to find cliques or independent sets of size
4342:
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Known algorithms for edge clique cover are probably optimal",
3530:
1435:
4396:
4136:
2979:
868:
Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in
2900:
2799:
2717:
2634:
4511:
4426:
28:
704:
20:
4658:
4628:
191:
4638:
2079:
1981:
1952:
4545:
2025:
such that satisfiability of conjunctive normal form formulas without clause length limits can be solved in
3879:
40th Annual
Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA
1706:
1643:
2983:
1120:, which posits that there is no family of algorithms (one for each length of the input, in the spirit of
978:
1169:
4612:
4576:
4555:
1592:
4653:
4344:
2450:
2030:
642:
512:
4571:
4409:
4073:
3948:
4028:
4014:; Paturi, Ramamohan; Zane, Francis (2001), "Which problems have strongly exponential complexity?",
3984:
3328:
3002:
2600:
1284:
3250:
proves the existence of NP-complete problems for which the best known running times have the form
4679:
3168:
2186:
1896:
1358:
1024:
199:
115:
3638:
2402:
1857:
1793:
82:
4404:
4068:
4023:
3979:
3943:
3752:
2974:
Equivalently, any improvement on these running times would falsify the strong exponential time
1497:
Therefore, if the exponential time hypothesis is true, there must be infinitely many values of
3253:
3105:
2978:
The exponential time hypothesis also implies that any fixed-parameter tractable algorithm for
2339:
2252:
1129:
1081:
913:
873:
46:
4540:
4530:
4525:
3775:
proves the nonexistence of the family of circuits and the separation of these two complexity
3447:
3243:
2008:
1549:
1413:
597:
432:
3731:
exists, and a family of circuits simulating NEXPTIME in P/poly also existed, then algorithm
3582:
3333:
It is an important open problem in this area whether this implication can be reversed: does
3297:
1829:
4648:
4375:
4140:
4055:
3787:
2121:
2076:. However, if the strong exponential time hypothesis fails, it would still be possible for
1923:
1520:
1331:
1052:
951:
836:
566:
460:
3073:
8:
4011:
3971:
3814:
3239:
2114:
The exponential time hypothesis implies that many other problems in the complexity class
1121:
153:
40:
4642:
4632:
4458:, Lecture Notes in Computer Science, vol. 6175, Springer-Verlag, pp. 313–325,
4067:, Lecture Notes in Computer Science, vol. 2570, Springer-Verlag, pp. 185–207,
3974:; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits",
4432:
4379:
4353:
4325:
4307:
4261:
4233:
4096:
3890:
3860:
3840:
3758:
3734:
3714:
3684:
3618:
3501:
3477:
3342:
3207:
3144:
3045:
2877:
2612:
2378:
2317:
2297:
2230:
2197:
2150:
2069:
1769:
1746:
1683:
1621:
1500:
1387:
683:
618:
488:
405:
384:
290:
265:
241:
213:
195:
171:
4454:
Dantsin, Evgeny; Wolpert, Alexander (2010), "On moderately exponential time for SAT",
3010:
4480:
4467:
4422:
4283:
4251:
4086:
3919:
3830:
2178:
79:. More precisely, the usual form of the hypothesis asserts the existence of a number
4383:
4265:
4607:
4459:
4414:
4363:
4329:
4317:
4243:
4202:
4171:
4078:
4033:
3989:
3953:
3894:
3882:
3822:
3791:
3247:
2446:
2115:
2073:
259:
231:
4436:
4100:
3918:, EATCS Texts in Theoretical Computer Science, Springer-Verlag, pp. 417–451,
3844:
2287:
The exponential time hypothesis also implies that it is not possible to solve the
4463:
4371:
4221:
4104:
112:
such that all algorithms that correctly solve this problem require time at least
4247:
3993:
3957:
4684:
4602:
4321:
4207:
3942:, Lecture Notes in Computer Science, vol. 7535, Springer, pp. 13–24,
2709:
2374:
The strong exponential time hypothesis implies that it is not possible to find
2182:
2170:
1742:
3-CNF formulas, each with a linear number of variables, such that the original
3886:
4699:
4082:
4418:
4399:(2010), "Improving exhaustive search implies superpolynomial lower bounds",
3826:
3064:
communications protocol would be for one of the three parties to transmit a
4176:
4037:
3911:
3441:
3431:{\displaystyle {\mathsf {M}}\subseteq {\mathsf {W}}\subseteq {\mathsf {M}}}
2998:
2190:
1213:
1076:
would equal zero even though there would be no single algorithm running in
4535:
4159:
2792:
235:
832:
that they are all nonzero, or equivalently, that the smallest of them,
829:
4367:
817:{\displaystyle s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.}
4162:; Kilian, Joe (1997), "On limited versus polynomial nondeterminism",
3978:, Lecture Notes in Computer Science, vol. 5917, pp. 75–85,
3065:
2604:
3523:
The exponential time hypothesis is equivalent to the statement that
2599:
The strong exponential time hypothesis leads to tight bounds on the
3704:
4358:
4312:
4238:
591:
283:
4304:
Proc. 22nd ACM/SIAM Symposium on
Discrete Algorithms (SODA 2011)
4142:
Proc. 21st ACM/SIAM Symposium on
Discrete Algorithms (SODA 2010)
3708:
2445:
The exponential time hypothesis implies also that the weighted
1583:
An important tool in this area is the sparsification lemma of
2588:{\textstyle O(2^{O({\sqrt {\operatorname {OPT} }})}n^{O(1)})}
2516:{\textstyle O(2^{o({\sqrt {\operatorname {OPT} }})}n^{O(1)})}
36:
2525:
It does however have a parameterized algorithm with running
1216:
that is bounded above by one, they must converge to a limit
1116:
A related variant of the exponential time hypothesis is the
4401:
Proc. 42nd ACM Symposium on Theory of
Computing (STOC 2010)
4277:
4058:(2003), "Exact algorithms for NP-hard problems: A survey",
3914:(2006), "16. Subexponential Fixed-Parameter Tractability",
3242:. More strongly, in this case, 3-SAT could not even have a
2288:
152:
The exponential time hypothesis, if true, would imply that
4456:
374:{\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}
3790:, showing that a similar exponential gap cannot hold for
2118:
do not have algorithms whose running time is faster than
262:, with the base of the exponential function depending on
3969:
4341:
4139:(2010), "On the possibility of faster SAT algorithms",
3817:; Paturi, Ramamohan (1999), "The Complexity of k-SAT",
4510:
3256:
3140:
it could be transformed into an algorithm for solving
2903:
2802:
2720:
2637:
2533:
2461:
1887:
as well, and the exponential time hypothesis would be
1268:{\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}
4301:
4010:
3863:
3857:
Schöning, Uwe (1999), "A probabilistic algorithm for
3761:
3737:
3717:
3687:
3641:
3621:
3585:
3533:
3504:
3480:
3450:
3367:
3345:
3300:
3210:
3171:
3147:
3108:
3076:
3048:
3013:
2880:
2615:
2405:
2381:
2342:
2320:
2300:
2255:
2233:
2200:
2153:
2124:
2082:
2033:
2011:
1984:
1955:
1926:
1899:
1860:
1832:
1796:
1772:
1749:
1709:
1686:
1646:
1624:
1595:
1584:
1552:
1523:
1503:
1438:
1416:
1407:
1390:
1361:
1334:
1287:
1222:
1172:
1132:
1084:
1055:
1027:
981:
954:
916:
876:
839:
755:
707:
686:
645:
621:
600:
569:
515:
491:
463:
435:
408:
387:
315:
293:
268:
244:
216:
174:
118:
85:
49:
3572:{\displaystyle {\mathsf {M}}\subseteq {\mathsf {W}}}
2453:
does not have a parametrized algorithm with running
3635:that solves Boolean circuit satisfiability in time
3869:
3767:
3743:
3723:
3693:
3671:
3627:
3597:
3571:
3510:
3486:
3465:
3430:
3351:
3312:
3285:
3216:
3193:
3153:
3130:
3091:
3054:
3031:
2964:
2886:
2863:
2781:
2698:
2621:
2587:
2515:
2433:
2387:
2364:
2326:
2306:
2277:
2239:
2206:
2159:
2137:
2095:
2058:
2017:
1997:
1968:
1939:
1912:
1879:
1844:
1815:
1778:
1755:
1734:
1692:
1671:
1630:
1607:
1571:
1536:
1509:
1488:{\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}
1487:
1422:
1396:
1374:
1347:
1306:
1267:
1204:
1154:
1106:
1068:
1040:
1013:
967:
938:
898:
852:
816:
739:
692:
670:
627:
606:
582:
553:
497:
476:
447:
414:
393:
373:
299:
274:
250:
222:
180:
144:
104:
71:
3937:
3819:Proc. 14th IEEE Conf. on Computational Complexity
3813:
2965:{\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}
2864:{\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}
2782:{\textstyle {\bigl (}3-o(1){\bigr )}^{w}n^{O(1)}}
2699:{\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}
32:
4697:
4192:
4131:
4061:Combinatorial Optimization — Eureka, You Shrink!
1237:
908:If there existed an algorithm to solve 3-SAT in
4220:
4164:Chicago Journal of Theoretical Computer Science
2603:of several graph problems on graphs of bounded
700:cannot be easier, these numbers are ordered as
238:algorithm, but all known algorithms for larger
210:of variables and their negations) with at most
4453:
1788:in subexponential time as well. Equivalently,
4496:
2932:
2906:
2831:
2805:
2749:
2723:
2666:
2640:
4403:, New York, NY, USA: ACM, pp. 231–240,
3877:-SAT and constraint satisfaction problems",
4158:
3881:, IEEE Computer Society, pp. 410–414,
2992:
740:{\displaystyle s_{3}\leq s_{4}\leq \cdots }
4503:
4489:
16:Unproven computational hardness assumption
4408:
4357:
4311:
4237:
4206:
4175:
4072:
4054:
4027:
3983:
3947:
3909:
4395:
3856:
3755:. Therefore, the existence of algorithm
3612:
3233:
3005:, three subsets of the integers in some
2109:
2096:{\displaystyle s_{\operatorname {CNF} }}
1998:{\displaystyle s_{\operatorname {CNF} }}
1969:{\displaystyle s_{\operatorname {CNF} }}
749:and because of WalkSAT they are at most
401:is the number of variables in the given
37:satisfiability of 3-CNF Boolean formulas
4195:Journal of Computer and System Sciences
4188:
4186:
4016:Journal of Computer and System Sciences
4006:
4004:
4002:
3440:for instance, the problem of finding a
1118:non-uniform exponential time hypothesis
194:in which the input to the problem is a
4698:
4127:
4125:
4123:
3809:
3807:
3555:
3536:
3408:
3389:
3370:
4484:
4228:, Lecture Notes in Computer Science,
4050:
4048:
4046:
2397:dominating sets more quickly than in
1585:Impagliazzo, Paturi & Zane (2001)
1408:Impagliazzo, Paturi & Zane (2001)
4183:
3999:
3905:
3903:
3711:. Williams shows that, if algorithm
3615:shows, if there exists an algorithm
1735:{\displaystyle O(2^{\varepsilon n})}
1672:{\displaystyle O(2^{\varepsilon n})}
484:to be the smallest number such that
4389:
4335:
4295:
4271:
4120:
3804:
3679:for some superpolynomially growing
1014:{\displaystyle O(2^{\delta _{i}n})}
13:
4706:Computational hardness assumptions
4512:Computational hardness assumptions
4446:
4214:
4043:
3963:
3931:
3850:
1905:
1457:
1367:
1293:
1277:strong exponential time hypothesis
1247:
1228:
1205:{\displaystyle s_{3},s_{4},\dots }
286:probabilistic algorithm can solve
14:
4717:
4152:
3900:
1608:{\displaystyle \varepsilon >0}
1323:
29:computational hardness assumption
4551:Decisional composite residuosity
1410:showed, there exists a constant
3916:Parameterized Complexity Theory
2059:{\displaystyle O(2^{\delta n})}
1318:
671:{\displaystyle O(2^{\delta n})}
554:{\displaystyle 2^{s_{k}n+o(n)}}
33:Impagliazzo & Paturi (1999)
21:computational complexity theory
3666:
3660:
3566:
3560:
3547:
3541:
3527:, and the question of whether
3425:
3413:
3400:
3394:
3381:
3375:
3280:
3260:
3188:
3175:
3123:
3117:
3086:
3080:
3026:
3014:
2957:
2951:
2926:
2920:
2856:
2850:
2825:
2819:
2774:
2768:
2743:
2737:
2691:
2685:
2660:
2654:
2582:
2577:
2571:
2558:
2548:
2537:
2510:
2505:
2499:
2486:
2476:
2465:
2426:
2420:
2357:
2351:
2270:
2264:
2053:
2037:
2005:is the infimum of the numbers
1729:
1713:
1666:
1650:
1482:
1462:
1244:
1147:
1141:
1099:
1093:
1008:
985:
931:
925:
891:
885:
665:
649:
546:
540:
363:
357:
192:Boolean satisfiability problem
64:
58:
1:
2334:of them that add to zero) in
1307:{\displaystyle s_{\infty }=1}
680:Because problems with larger
162:
4587:Computational Diffie–Hellman
4464:10.1007/978-3-642-14186-7_27
190:problem is a version of the
7:
4675:Exponential time hypothesis
4248:10.1007/978-3-642-17517-6_3
3994:10.1007/978-3-642-11269-0_6
3958:10.1007/978-3-642-33293-7_4
3781:
3194:{\displaystyle O(1.74^{n})}
1920:of the sequence of numbers
1913:{\displaystyle s_{\infty }}
1640:formula can be replaced by
1375:{\displaystyle s_{\infty }}
1041:{\displaystyle \delta _{i}}
826:exponential time hypothesis
145:{\displaystyle 2^{s_{3}n}.}
25:exponential time hypothesis
10:
4722:
4322:10.1137/1.9781611973082.61
4208:10.1016/j.jcss.2006.04.007
3672:{\displaystyle 2^{n}/f(n)}
2434:{\displaystyle n^{k-o(1)}}
1880:{\displaystyle s_{3}>0}
1816:{\displaystyle s_{k}>0}
1124:) that can solve 3-SAT in
1021:for a sequence of numbers
105:{\displaystyle s_{3}>0}
4685:Planted clique conjecture
4667:
4654:Ring learning with errors
4621:
4595:
4582:Decisional Diffie–Hellman
4564:
4518:
4345:SIAM Journal on Computing
4282:, Springer, p. 555,
3887:10.1109/SFFCS.1999.814612
3286:{\textstyle O(2^{n^{c}})}
2873:and the optimum time for
2708:the optimal time for the
1279:(SETH) is the conjecture
4280:Parameterized Algorithms
4226:Proc. ISAAC 2010, Part I
4083:10.1007/3-540-36478-1_17
3797:
3131:{\displaystyle 2^{o(m)}}
3003:communication complexity
2993:Communication complexity
2601:parameterized complexity
2365:{\displaystyle n^{o(k)}}
2278:{\displaystyle n^{o(k)}}
2187:maximum independent sets
1587:, which shows that, for
1155:{\displaystyle 2^{o(n)}}
1107:{\displaystyle 2^{o(n)}}
939:{\displaystyle 2^{o(n)}}
899:{\displaystyle 2^{o(n)}}
72:{\displaystyle 2^{o(n)}}
4680:Unique games conjecture
4629:Shortest vector problem
4603:External Diffie–Hellman
4419:10.1145/1806689.1806723
3827:10.1109/CCC.1999.766282
3466:{\displaystyle k\log n}
2997:In the three-party set
2169:These problems include
2018:{\displaystyle \delta }
1572:{\displaystyle s_{k+1}}
1423:{\displaystyle \alpha }
1328:It is not possible for
607:{\displaystyle \delta }
448:{\displaystyle k\geq 3}
200:conjunctive normal form
31:that was formulated by
4659:Short integer solution
4639:Closest vector problem
4177:10.4086/cjtcs.1997.001
4038:10.1006/jcss.2001.1774
3871:
3769:
3753:time hierarchy theorem
3745:
3725:
3695:
3673:
3629:
3599:
3598:{\displaystyle i>1}
3573:
3512:
3488:
3467:
3432:
3353:
3314:
3313:{\displaystyle c<1}
3287:
3218:
3195:
3155:
3132:
3093:
3056:
3033:
2966:
2888:
2865:
2783:
2700:
2623:
2589:
2517:
2435:
2389:
2366:
2328:
2308:
2279:
2241:
2208:
2161:
2139:
2097:
2060:
2019:
1999:
1970:
1941:
1914:
1881:
1846:
1845:{\displaystyle k>0}
1817:
1780:
1757:
1736:
1694:
1673:
1632:
1609:
1573:
1538:
1511:
1489:
1424:
1398:
1376:
1349:
1308:
1269:
1206:
1156:
1108:
1070:
1042:
1015:
969:
940:
900:
854:
818:
741:
694:
672:
629:
608:
584:
555:
499:
478:
449:
416:
395:
375:
301:
276:
252:
224:
182:
146:
106:
73:
4546:Quadratic residuosity
4526:Integer factorization
3872:
3770:
3746:
3726:
3696:
3674:
3630:
3600:
3574:
3513:
3489:
3468:
3433:
3354:
3315:
3288:
3244:quasi-polynomial time
3234:Structural complexity
3219:
3196:
3156:
3133:
3094:
3057:
3034:
2967:
2889:
2866:
2791:the optimum time for
2784:
2701:
2624:
2590:
2518:
2436:
2390:
2367:
2329:
2309:
2280:
2242:
2209:
2162:
2140:
2138:{\displaystyle c^{n}}
2110:Other search problems
2098:
2061:
2020:
2000:
1971:
1942:
1940:{\displaystyle s_{k}}
1915:
1882:
1847:
1818:
1781:
1758:
1737:
1695:
1674:
1633:
1610:
1574:
1539:
1537:{\displaystyle s_{k}}
1512:
1490:
1425:
1399:
1377:
1350:
1348:{\displaystyle s_{k}}
1309:
1270:
1207:
1157:
1109:
1071:
1069:{\displaystyle s_{3}}
1043:
1016:
970:
968:{\displaystyle s_{3}}
941:
901:
855:
853:{\displaystyle s_{3}}
819:
742:
695:
673:
630:
609:
585:
583:{\displaystyle s_{k}}
556:
500:
479:
477:{\displaystyle s_{k}}
450:
417:
396:
376:
302:
277:
253:
225:
183:
147:
107:
74:
4649:Learning with errors
4306:, pp. 777–789,
4148:, pp. 1065–1075
4012:Impagliazzo, Russell
3861:
3821:, pp. 237–240,
3815:Impagliazzo, Russell
3759:
3735:
3715:
3685:
3639:
3619:
3583:
3531:
3502:
3478:
3448:
3365:
3343:
3298:
3254:
3208:
3169:
3145:
3106:
3092:{\displaystyle o(m)}
3074:
3046:
3041:nonempty. A trivial
3011:
2901:
2878:
2800:
2718:
2635:
2613:
2531:
2459:
2403:
2379:
2340:
2318:
2298:
2253:
2231:
2198:
2151:
2122:
2080:
2031:
2009:
1982:
1953:
1924:
1897:
1893:The limiting value
1858:
1830:
1794:
1770:
1747:
1707:
1684:
1644:
1622:
1593:
1550:
1521:
1501:
1436:
1414:
1388:
1359:
1332:
1285:
1220:
1170:
1166:Because the numbers
1130:
1082:
1053:
1025:
979:
952:
914:
874:
837:
753:
705:
684:
643:
619:
598:
594:of the real numbers
567:
513:
489:
461:
433:
406:
385:
313:
291:
282:. For instance, the
266:
242:
214:
172:
116:
83:
47:
39:cannot be solved in
3972:Impagliazzo, Russel
3707:is not a subset of
2314:real numbers, find
41:subexponential time
4572:Discrete logarithm
4556:Higher residuosity
4056:Woeginger, Gerhard
3867:
3765:
3741:
3721:
3691:
3669:
3625:
3595:
3569:
3508:
3484:
3463:
3428:
3349:
3310:
3283:
3214:
3191:
3151:
3128:
3089:
3052:
3029:
2986:dependence on the
2984:double exponential
2962:
2884:
2861:
2779:
2696:
2619:
2585:
2513:
2431:
2385:
2362:
2324:
2304:
2275:
2237:
2204:
2179:Hamiltonian cycles
2157:
2135:
2093:
2072:over all possible
2070:brute-force search
2056:
2015:
1995:
1966:
1937:
1910:
1877:
1842:
1813:
1776:
1753:
1732:
1690:
1669:
1628:
1605:
1569:
1534:
1507:
1485:
1420:
1394:
1372:
1345:
1304:
1265:
1251:
1214:monotonic sequence
1202:
1152:
1104:
1066:
1038:
1011:
965:
936:
896:
850:
814:
737:
690:
668:
625:
604:
580:
551:
495:
474:
445:
412:
391:
371:
297:
272:
248:
220:
196:Boolean expression
178:
142:
102:
69:
4693:
4692:
4668:Non-cryptographic
4473:978-3-642-14185-0
4368:10.1137/130947076
4289:978-3-319-21274-6
4257:978-3-642-17516-9
4092:978-3-540-00580-3
3925:978-3-540-29952-3
3870:{\displaystyle k}
3836:978-0-7695-0075-1
3788:Savitch's theorem
3768:{\displaystyle A}
3744:{\displaystyle A}
3724:{\displaystyle A}
3694:{\displaystyle f}
3628:{\displaystyle A}
3511:{\displaystyle k}
3487:{\displaystyle n}
3352:{\displaystyle i}
3217:{\displaystyle k}
3154:{\displaystyle k}
3055:{\displaystyle m}
2980:edge clique cover
2887:{\displaystyle k}
2622:{\displaystyle w}
2556:
2484:
2388:{\displaystyle k}
2327:{\displaystyle k}
2307:{\displaystyle n}
2240:{\displaystyle k}
2207:{\displaystyle n}
2160:{\displaystyle c}
2074:truth assignments
1947:is at most equal
1779:{\displaystyle k}
1756:{\displaystyle k}
1693:{\displaystyle k}
1631:{\displaystyle k}
1510:{\displaystyle k}
1397:{\displaystyle k}
1236:
801:
693:{\displaystyle k}
637:can be solved in
628:{\displaystyle k}
507:can be solved in
498:{\displaystyle k}
415:{\displaystyle k}
394:{\displaystyle n}
336:
300:{\displaystyle k}
275:{\displaystyle k}
251:{\displaystyle k}
223:{\displaystyle k}
181:{\displaystyle k}
35:. It states that
4713:
4608:Sub-group hiding
4519:Number theoretic
4505:
4498:
4491:
4482:
4481:
4476:
4440:
4439:
4412:
4393:
4387:
4386:
4361:
4339:
4333:
4332:
4315:
4299:
4293:
4292:
4275:
4269:
4268:
4241:
4222:Karpinski, Marek
4218:
4212:
4211:
4210:
4201:(8): 1346–1367,
4190:
4181:
4180:
4179:
4156:
4150:
4149:
4147:
4129:
4118:
4117:
4116:
4115:
4109:
4103:, archived from
4076:
4066:
4052:
4041:
4040:
4031:
4008:
3997:
3996:
3987:
3970:Calabro, Chris;
3967:
3961:
3960:
3951:
3935:
3929:
3928:
3907:
3898:
3897:
3876:
3874:
3873:
3868:
3854:
3848:
3847:
3811:
3792:space complexity
3778:
3774:
3772:
3771:
3766:
3750:
3748:
3747:
3742:
3730:
3728:
3727:
3722:
3702:
3700:
3698:
3697:
3692:
3678:
3676:
3675:
3670:
3656:
3651:
3650:
3634:
3632:
3631:
3626:
3608:
3604:
3602:
3601:
3596:
3578:
3576:
3575:
3570:
3559:
3558:
3540:
3539:
3526:
3522:
3518:
3517:
3515:
3514:
3509:
3495:
3493:
3491:
3490:
3485:
3472:
3470:
3469:
3464:
3439:
3437:
3435:
3434:
3429:
3412:
3411:
3393:
3392:
3374:
3373:
3360:
3358:
3356:
3355:
3350:
3336:
3332:
3321:
3319:
3317:
3316:
3311:
3292:
3290:
3289:
3284:
3279:
3278:
3277:
3276:
3248:padding argument
3230:
3225:
3223:
3221:
3220:
3215:
3201:
3200:
3198:
3197:
3192:
3187:
3186:
3162:
3160:
3158:
3157:
3152:
3139:
3137:
3135:
3134:
3129:
3127:
3126:
3100:
3098:
3096:
3095:
3090:
3063:
3061:
3059:
3058:
3053:
3039:
3038:
3036:
3035:
3032:{\displaystyle }
3030:
2989:
2977:
2973:
2971:
2969:
2968:
2963:
2961:
2960:
2942:
2941:
2936:
2935:
2910:
2909:
2895:
2893:
2891:
2890:
2885:
2872:
2870:
2868:
2867:
2862:
2860:
2859:
2841:
2840:
2835:
2834:
2809:
2808:
2790:
2788:
2786:
2785:
2780:
2778:
2777:
2759:
2758:
2753:
2752:
2727:
2726:
2707:
2705:
2703:
2702:
2697:
2695:
2694:
2676:
2675:
2670:
2669:
2644:
2643:
2629:
2628:
2626:
2625:
2620:
2596:
2594:
2592:
2591:
2586:
2581:
2580:
2562:
2561:
2557:
2552:
2524:
2522:
2520:
2519:
2514:
2509:
2508:
2490:
2489:
2485:
2480:
2447:feedback arc set
2442:
2440:
2438:
2437:
2432:
2430:
2429:
2396:
2394:
2392:
2391:
2386:
2373:
2371:
2369:
2368:
2363:
2361:
2360:
2333:
2331:
2330:
2325:
2313:
2311:
2310:
2305:
2291:
2286:
2284:
2282:
2281:
2276:
2274:
2273:
2246:
2244:
2243:
2238:
2226:
2219:
2215:
2213:
2211:
2210:
2205:
2174:
2168:
2166:
2164:
2163:
2158:
2144:
2142:
2141:
2136:
2134:
2133:
2106:
2102:
2100:
2099:
2094:
2092:
2091:
2067:
2065:
2063:
2062:
2057:
2052:
2051:
2024:
2022:
2021:
2016:
2004:
2002:
2001:
1996:
1994:
1993:
1977:
1975:
1973:
1972:
1967:
1965:
1964:
1946:
1944:
1943:
1938:
1936:
1935:
1919:
1917:
1916:
1911:
1909:
1908:
1890:
1886:
1884:
1883:
1878:
1870:
1869:
1853:
1851:
1849:
1848:
1843:
1823:
1822:
1820:
1819:
1814:
1806:
1805:
1787:
1785:
1783:
1782:
1777:
1764:
1762:
1760:
1759:
1754:
1741:
1739:
1738:
1733:
1728:
1727:
1701:
1699:
1697:
1696:
1691:
1678:
1676:
1675:
1670:
1665:
1664:
1639:
1637:
1635:
1634:
1629:
1616:
1614:
1612:
1611:
1606:
1580:
1578:
1576:
1575:
1570:
1568:
1567:
1543:
1541:
1540:
1535:
1533:
1532:
1516:
1514:
1513:
1508:
1496:
1494:
1492:
1491:
1486:
1478:
1461:
1460:
1448:
1447:
1429:
1427:
1426:
1421:
1405:
1403:
1401:
1400:
1395:
1381:
1379:
1378:
1373:
1371:
1370:
1354:
1352:
1351:
1346:
1344:
1343:
1315:
1313:
1311:
1310:
1305:
1297:
1296:
1274:
1272:
1271:
1266:
1261:
1260:
1250:
1232:
1231:
1211:
1209:
1208:
1203:
1195:
1194:
1182:
1181:
1163:
1161:
1159:
1158:
1153:
1151:
1150:
1115:
1113:
1111:
1110:
1105:
1103:
1102:
1075:
1073:
1072:
1067:
1065:
1064:
1047:
1045:
1044:
1039:
1037:
1036:
1020:
1018:
1017:
1012:
1007:
1006:
1002:
1001:
974:
972:
971:
966:
964:
963:
947:
945:
943:
942:
937:
935:
934:
907:
905:
903:
902:
897:
895:
894:
865:
861:
859:
857:
856:
851:
849:
848:
823:
821:
820:
815:
807:
803:
802:
794:
778:
777:
765:
764:
748:
746:
744:
743:
738:
730:
729:
717:
716:
699:
697:
696:
691:
679:
677:
675:
674:
669:
664:
663:
636:
634:
632:
631:
626:
613:
611:
610:
605:
589:
587:
586:
581:
579:
578:
562:
560:
558:
557:
552:
550:
549:
530:
529:
506:
504:
502:
501:
496:
483:
481:
480:
475:
473:
472:
456:
454:
452:
451:
446:
426:
423:
421:
419:
418:
413:
400:
398:
397:
392:
380:
378:
377:
372:
367:
366:
348:
347:
342:
338:
337:
329:
309:in average time
308:
306:
304:
303:
298:
281:
279:
278:
273:
260:exponential time
257:
255:
254:
249:
229:
227:
226:
221:
189:
187:
185:
184:
179:
159:
151:
149:
148:
143:
138:
137:
133:
132:
111:
109:
108:
103:
95:
94:
78:
76:
75:
70:
68:
67:
4721:
4720:
4716:
4715:
4714:
4712:
4711:
4710:
4696:
4695:
4694:
4689:
4663:
4617:
4613:Decision linear
4591:
4565:Group theoretic
4560:
4514:
4509:
4479:
4474:
4449:
4447:Further reading
4444:
4443:
4429:
4410:10.1.1.216.1299
4394:
4390:
4340:
4336:
4300:
4296:
4290:
4276:
4272:
4258:
4219:
4215:
4191:
4184:
4157:
4153:
4145:
4133:Pătraşcu, Mihai
4130:
4121:
4113:
4111:
4107:
4093:
4074:10.1.1.168.5383
4064:
4053:
4044:
4009:
4000:
3968:
3964:
3949:10.1.1.680.8401
3936:
3932:
3926:
3908:
3901:
3862:
3859:
3858:
3855:
3851:
3837:
3812:
3805:
3800:
3784:
3776:
3760:
3757:
3756:
3736:
3733:
3732:
3716:
3713:
3712:
3686:
3683:
3682:
3680:
3652:
3646:
3642:
3640:
3637:
3636:
3620:
3617:
3616:
3613:Williams (2010)
3606:
3584:
3581:
3580:
3554:
3553:
3535:
3534:
3532:
3529:
3528:
3524:
3520:
3503:
3500:
3499:
3497:
3479:
3476:
3475:
3474:
3449:
3446:
3445:
3407:
3406:
3388:
3387:
3369:
3368:
3366:
3363:
3362:
3361:
3344:
3341:
3340:
3338:
3334:
3327:
3299:
3296:
3295:
3293:
3272:
3268:
3267:
3263:
3255:
3252:
3251:
3236:
3228:
3209:
3206:
3205:
3203:
3182:
3178:
3170:
3167:
3166:
3164:
3146:
3143:
3142:
3141:
3113:
3109:
3107:
3104:
3103:
3102:
3075:
3072:
3071:
3070:
3047:
3044:
3043:
3042:
3012:
3009:
3008:
3006:
2995:
2987:
2975:
2947:
2943:
2937:
2931:
2930:
2929:
2905:
2904:
2902:
2899:
2898:
2896:
2879:
2876:
2875:
2874:
2846:
2842:
2836:
2830:
2829:
2828:
2804:
2803:
2801:
2798:
2797:
2795:
2764:
2760:
2754:
2748:
2747:
2746:
2722:
2721:
2719:
2716:
2715:
2713:
2681:
2677:
2671:
2665:
2664:
2663:
2639:
2638:
2636:
2633:
2632:
2630:
2614:
2611:
2610:
2608:
2567:
2563:
2551:
2544:
2540:
2532:
2529:
2528:
2526:
2495:
2491:
2479:
2472:
2468:
2460:
2457:
2456:
2454:
2410:
2406:
2404:
2401:
2400:
2398:
2380:
2377:
2376:
2375:
2347:
2343:
2341:
2338:
2337:
2335:
2319:
2316:
2315:
2299:
2296:
2295:
2294:problem (given
2289:
2260:
2256:
2254:
2251:
2250:
2248:
2232:
2229:
2228:
2225:non-polynomial.
2224:
2217:
2199:
2196:
2195:
2194:
2183:maximum cliques
2172:
2152:
2149:
2148:
2146:
2129:
2125:
2123:
2120:
2119:
2112:
2104:
2087:
2083:
2081:
2078:
2077:
2044:
2040:
2032:
2029:
2028:
2026:
2010:
2007:
2006:
1989:
1985:
1983:
1980:
1979:
1960:
1956:
1954:
1951:
1950:
1948:
1931:
1927:
1925:
1922:
1921:
1904:
1900:
1898:
1895:
1894:
1888:
1865:
1861:
1859:
1856:
1855:
1831:
1828:
1827:
1825:
1801:
1797:
1795:
1792:
1791:
1789:
1771:
1768:
1767:
1766:
1748:
1745:
1744:
1743:
1720:
1716:
1708:
1705:
1704:
1685:
1682:
1681:
1680:
1657:
1653:
1645:
1642:
1641:
1623:
1620:
1619:
1618:
1594:
1591:
1590:
1588:
1557:
1553:
1551:
1548:
1547:
1545:
1528:
1524:
1522:
1519:
1518:
1502:
1499:
1498:
1474:
1456:
1452:
1443:
1439:
1437:
1434:
1433:
1431:
1415:
1412:
1411:
1389:
1386:
1385:
1383:
1366:
1362:
1360:
1357:
1356:
1339:
1335:
1333:
1330:
1329:
1326:
1321:
1292:
1288:
1286:
1283:
1282:
1280:
1256:
1252:
1240:
1227:
1223:
1221:
1218:
1217:
1190:
1186:
1177:
1173:
1171:
1168:
1167:
1137:
1133:
1131:
1128:
1127:
1125:
1089:
1085:
1083:
1080:
1079:
1077:
1060:
1056:
1054:
1051:
1050:
1032:
1028:
1026:
1023:
1022:
997:
993:
992:
988:
980:
977:
976:
959:
955:
953:
950:
949:
921:
917:
915:
912:
911:
909:
881:
877:
875:
872:
871:
869:
863:
844:
840:
838:
835:
834:
833:
793:
786:
782:
773:
769:
760:
756:
754:
751:
750:
725:
721:
712:
708:
706:
703:
702:
701:
685:
682:
681:
656:
652:
644:
641:
640:
638:
620:
617:
616:
615:
599:
596:
595:
574:
570:
568:
565:
564:
525:
521:
520:
516:
514:
511:
510:
508:
490:
487:
486:
485:
468:
464:
462:
459:
458:
434:
431:
430:
428:
424:
407:
404:
403:
402:
386:
383:
382:
353:
349:
343:
328:
321:
317:
316:
314:
311:
310:
292:
289:
288:
287:
267:
264:
263:
243:
240:
239:
215:
212:
211:
173:
170:
169:
168:
165:
157:
128:
124:
123:
119:
117:
114:
113:
90:
86:
84:
81:
80:
54:
50:
48:
45:
44:
27:is an unproven
17:
12:
11:
5:
4719:
4709:
4708:
4691:
4690:
4688:
4687:
4682:
4677:
4671:
4669:
4665:
4664:
4662:
4661:
4656:
4651:
4646:
4636:
4625:
4623:
4619:
4618:
4616:
4615:
4610:
4605:
4599:
4597:
4593:
4592:
4590:
4589:
4584:
4579:
4577:Diffie-Hellman
4574:
4568:
4566:
4562:
4561:
4559:
4558:
4553:
4548:
4543:
4538:
4533:
4528:
4522:
4520:
4516:
4515:
4508:
4507:
4500:
4493:
4485:
4478:
4477:
4472:
4450:
4448:
4445:
4442:
4441:
4427:
4397:Williams, Ryan
4388:
4334:
4294:
4288:
4270:
4256:
4213:
4182:
4151:
4137:Williams, Ryan
4119:
4091:
4042:
4029:10.1.1.66.3717
4022:(4): 512–530,
3998:
3985:10.1.1.331.764
3962:
3930:
3924:
3899:
3866:
3849:
3835:
3802:
3801:
3799:
3796:
3795:
3794:
3783:
3780:
3764:
3740:
3720:
3690:
3668:
3665:
3662:
3659:
3655:
3649:
3645:
3624:
3594:
3591:
3588:
3568:
3565:
3562:
3557:
3552:
3549:
3546:
3543:
3538:
3507:
3483:
3462:
3459:
3456:
3453:
3427:
3424:
3421:
3418:
3415:
3410:
3405:
3402:
3399:
3396:
3391:
3386:
3383:
3380:
3377:
3372:
3348:
3309:
3306:
3303:
3282:
3275:
3271:
3266:
3262:
3259:
3235:
3232:
3213:
3202:for any fixed
3190:
3185:
3181:
3177:
3174:
3150:
3125:
3122:
3119:
3116:
3112:
3088:
3085:
3082:
3079:
3051:
3028:
3025:
3022:
3019:
3016:
2994:
2991:
2959:
2956:
2953:
2950:
2946:
2940:
2934:
2928:
2925:
2922:
2919:
2916:
2913:
2908:
2883:
2858:
2855:
2852:
2849:
2845:
2839:
2833:
2827:
2824:
2821:
2818:
2815:
2812:
2807:
2776:
2773:
2770:
2767:
2763:
2757:
2751:
2745:
2742:
2739:
2736:
2733:
2730:
2725:
2710:dominating set
2693:
2690:
2687:
2684:
2680:
2674:
2668:
2662:
2659:
2656:
2653:
2650:
2647:
2642:
2618:
2584:
2579:
2576:
2573:
2570:
2566:
2560:
2555:
2550:
2547:
2543:
2539:
2536:
2512:
2507:
2504:
2501:
2498:
2494:
2488:
2483:
2478:
2475:
2471:
2467:
2464:
2428:
2425:
2422:
2419:
2416:
2413:
2409:
2384:
2359:
2356:
2353:
2350:
2346:
2323:
2303:
2272:
2269:
2266:
2263:
2259:
2236:
2203:
2156:
2132:
2128:
2111:
2108:
2090:
2086:
2055:
2050:
2047:
2043:
2039:
2036:
2014:
1992:
1988:
1963:
1959:
1934:
1930:
1907:
1903:
1876:
1873:
1868:
1864:
1841:
1838:
1835:
1812:
1809:
1804:
1800:
1775:
1752:
1731:
1726:
1723:
1719:
1715:
1712:
1689:
1668:
1663:
1660:
1656:
1652:
1649:
1627:
1604:
1601:
1598:
1566:
1563:
1560:
1556:
1531:
1527:
1506:
1484:
1481:
1477:
1473:
1470:
1467:
1464:
1459:
1455:
1451:
1446:
1442:
1419:
1393:
1369:
1365:
1342:
1338:
1325:
1324:Satisfiability
1322:
1320:
1317:
1303:
1300:
1295:
1291:
1264:
1259:
1255:
1249:
1246:
1243:
1239:
1235:
1230:
1226:
1201:
1198:
1193:
1189:
1185:
1180:
1176:
1149:
1146:
1143:
1140:
1136:
1101:
1098:
1095:
1092:
1088:
1063:
1059:
1035:
1031:
1010:
1005:
1000:
996:
991:
987:
984:
962:
958:
933:
930:
927:
924:
920:
893:
890:
887:
884:
880:
847:
843:
813:
810:
806:
800:
797:
792:
789:
785:
781:
776:
772:
768:
763:
759:
736:
733:
728:
724:
720:
715:
711:
689:
667:
662:
659:
655:
651:
648:
624:
603:
577:
573:
548:
545:
542:
539:
536:
533:
528:
524:
519:
494:
471:
467:
444:
441:
438:
411:
390:
370:
365:
362:
359:
356:
352:
346:
341:
335:
332:
327:
324:
320:
296:
271:
247:
219:
177:
164:
161:
141:
136:
131:
127:
122:
101:
98:
93:
89:
66:
63:
60:
57:
53:
15:
9:
6:
4:
3:
2:
4718:
4707:
4704:
4703:
4701:
4686:
4683:
4681:
4678:
4676:
4673:
4672:
4670:
4666:
4660:
4657:
4655:
4652:
4650:
4647:
4644:
4640:
4637:
4634:
4630:
4627:
4626:
4624:
4620:
4614:
4611:
4609:
4606:
4604:
4601:
4600:
4598:
4594:
4588:
4585:
4583:
4580:
4578:
4575:
4573:
4570:
4569:
4567:
4563:
4557:
4554:
4552:
4549:
4547:
4544:
4542:
4539:
4537:
4534:
4532:
4529:
4527:
4524:
4523:
4521:
4517:
4513:
4506:
4501:
4499:
4494:
4492:
4487:
4486:
4483:
4475:
4469:
4465:
4461:
4457:
4452:
4451:
4438:
4434:
4430:
4428:9781450300506
4424:
4420:
4416:
4411:
4406:
4402:
4398:
4392:
4385:
4381:
4377:
4373:
4369:
4365:
4360:
4355:
4351:
4347:
4346:
4338:
4331:
4327:
4323:
4319:
4314:
4309:
4305:
4298:
4291:
4285:
4281:
4274:
4267:
4263:
4259:
4253:
4249:
4245:
4240:
4235:
4231:
4227:
4223:
4217:
4209:
4204:
4200:
4196:
4189:
4187:
4178:
4173:
4169:
4165:
4161:
4155:
4144:
4143:
4138:
4134:
4128:
4126:
4124:
4110:on 2020-09-30
4106:
4102:
4098:
4094:
4088:
4084:
4080:
4075:
4070:
4063:
4062:
4057:
4051:
4049:
4047:
4039:
4035:
4030:
4025:
4021:
4017:
4013:
4007:
4005:
4003:
3995:
3991:
3986:
3981:
3977:
3973:
3966:
3959:
3955:
3950:
3945:
3941:
3934:
3927:
3921:
3917:
3913:
3912:Grohe, Martin
3906:
3904:
3896:
3892:
3888:
3884:
3880:
3864:
3853:
3846:
3842:
3838:
3832:
3828:
3824:
3820:
3816:
3810:
3808:
3803:
3793:
3789:
3786:
3785:
3779:
3762:
3754:
3738:
3718:
3710:
3706:
3688:
3663:
3657:
3653:
3647:
3643:
3622:
3614:
3609:
3592:
3589:
3586:
3563:
3550:
3544:
3505:
3481:
3460:
3457:
3454:
3451:
3443:
3422:
3419:
3416:
3403:
3397:
3384:
3378:
3346:
3330:
3324:
3307:
3304:
3301:
3273:
3269:
3264:
3257:
3249:
3245:
3241:
3231:
3211:
3183:
3179:
3172:
3148:
3120:
3114:
3110:
3099:communication
3083:
3077:
3067:
3049:
3023:
3020:
3017:
3004:
3000:
2990:
2985:
2981:
2954:
2948:
2944:
2938:
2923:
2917:
2914:
2911:
2881:
2853:
2847:
2843:
2837:
2822:
2816:
2813:
2810:
2794:
2771:
2765:
2761:
2755:
2740:
2734:
2731:
2728:
2711:
2688:
2682:
2678:
2672:
2657:
2651:
2648:
2645:
2616:
2606:
2602:
2597:
2574:
2568:
2564:
2553:
2545:
2541:
2534:
2502:
2496:
2492:
2481:
2473:
2469:
2462:
2452:
2448:
2443:
2423:
2417:
2414:
2411:
2407:
2382:
2354:
2348:
2344:
2321:
2301:
2293:
2267:
2261:
2257:
2234:
2223:problems are
2220:
2201:
2192:
2188:
2184:
2180:
2176:
2175:-colorability
2154:
2130:
2126:
2117:
2107:
2088:
2084:
2075:
2071:
2048:
2045:
2041:
2034:
2012:
1990:
1986:
1961:
1957:
1932:
1928:
1901:
1891:
1874:
1871:
1866:
1862:
1839:
1836:
1833:
1810:
1807:
1802:
1798:
1773:
1750:
1724:
1721:
1717:
1710:
1687:
1661:
1658:
1654:
1647:
1625:
1602:
1599:
1596:
1586:
1581:
1564:
1561:
1558:
1554:
1529:
1525:
1504:
1479:
1475:
1471:
1468:
1465:
1453:
1449:
1444:
1440:
1417:
1409:
1391:
1363:
1340:
1336:
1316:
1301:
1298:
1289:
1278:
1262:
1257:
1253:
1241:
1233:
1224:
1215:
1199:
1196:
1191:
1187:
1183:
1178:
1174:
1164:
1144:
1138:
1134:
1123:
1119:
1096:
1090:
1086:
1061:
1057:
1033:
1029:
1003:
998:
994:
989:
982:
960:
956:
928:
922:
918:
888:
882:
878:
866:
845:
841:
831:
827:
811:
808:
804:
798:
795:
790:
787:
783:
779:
774:
770:
766:
761:
757:
734:
731:
726:
722:
718:
713:
709:
687:
660:
657:
653:
646:
622:
601:
593:
575:
571:
543:
537:
534:
531:
526:
522:
517:
492:
469:
465:
442:
439:
436:
409:
388:
368:
360:
354:
350:
344:
339:
333:
330:
325:
322:
318:
294:
285:
269:
261:
245:
237:
233:
217:
209:
205:
202:(that is, an
201:
197:
193:
175:
160:
155:
139:
134:
129:
125:
120:
99:
96:
91:
87:
61:
55:
51:
42:
38:
34:
30:
26:
22:
4674:
4455:
4400:
4391:
4352:(1): 67–83,
4349:
4343:
4337:
4303:
4297:
4279:
4273:
4229:
4225:
4216:
4198:
4194:
4167:
4163:
4160:Feige, Uriel
4154:
4141:
4112:, retrieved
4105:the original
4060:
4019:
4015:
3975:
3965:
3939:
3933:
3915:
3910:Flum, Jörg;
3878:
3852:
3818:
3610:
3519:is complete
3442:vertex cover
3325:
3237:
3229:computation.
3138:computation,
2999:disjointness
2996:
2598:
2444:
2221:
2191:vertex cover
2113:
1892:
1582:
1327:
1319:Implications
1276:
1165:
1117:
867:
825:
207:
203:
166:
24:
18:
4536:RSA problem
3496:graph with
3001:problem in
2976:hypothesis.
2793:maximum cut
2451:tournaments
2449:problem on
236:linear time
158:complexity.
4541:Strong RSA
4531:Phi-hiding
4114:2011-03-31
3498:parameter
2988:parameter.
2982:must have
2609:treewidth
2177:, finding
1517:for which
830:conjecture
614:for which
590:to be the
163:Definition
4405:CiteSeerX
4359:1203.1754
4313:1007.5450
4239:1006.4396
4069:CiteSeerX
4024:CiteSeerX
3980:CiteSeerX
3944:CiteSeerX
3681:function
3551:⊆
3458:
3404:⊆
3385:⊆
3204:constant
3066:bitvector
2915:−
2894:-coloring
2814:−
2732:−
2649:−
2605:treewidth
2415:−
2147:constant
2145:for some
2103:to equal
2046:δ
2013:δ
1906:∞
1722:ε
1659:ε
1597:ε
1472:α
1469:−
1458:∞
1450:≤
1418:α
1368:∞
1355:to equal
1294:∞
1248:∞
1245:→
1229:∞
1200:…
1030:δ
995:δ
791:−
780:
767:≤
735:⋯
732:≤
719:≤
658:δ
602:δ
440:≥
427:For each
425:instance.
326:−
4700:Category
4622:Lattices
4596:Pairings
4384:11264145
4266:16512997
4232:: 3–14,
4170:: 1–20,
3782:See also
3777:classes.
3705:NEXPTIME
3605:is also
3444:of size
2712:problem
1679:simpler
1544:differs
1382:for any
864:nonzero.
429:integer
4376:3448348
4330:1810488
3895:1230959
3525:M ≠ FPT
3494:-vertex
3335:W ≠ FPT
3329:W ≠ FPT
2395:-vertex
2214:-vertex
1384:finite
1212:form a
828:is the
592:infimum
457:define
284:WalkSAT
4470:
4437:651703
4435:
4425:
4407:
4382:
4374:
4328:
4286:
4264:
4254:
4101:289357
4099:
4089:
4071:
4026:
3982:
3946:
3922:
3893:
3845:442454
3843:
3833:
3709:P/poly
3521:for M.
3473:in an
3240:P ≠ NP
3007:range
2218:false.
2189:, and
2171:graph
1978:where
1589:every
1122:advice
381:where
234:has a
154:P ≠ NP
23:, the
4433:S2CID
4380:S2CID
4354:arXiv
4326:S2CID
4308:arXiv
4262:S2CID
4234:arXiv
4146:(PDF)
4108:(PDF)
4097:S2CID
4065:(PDF)
3891:S2CID
3841:S2CID
3798:Notes
3703:then
3607:open.
3165:time
2527:time
2455:time
2399:time
2336:time
2249:time
2027:time
1889:true.
1854:then
1546:from
1432:that
1430:such
1281:that
1126:time
1078:time
948:then
910:time
870:time
639:time
509:time
258:take
232:2-SAT
4468:ISBN
4423:ISBN
4284:ISBN
4252:ISBN
4230:6506
4087:ISBN
3920:ISBN
3831:ISBN
3590:>
3579:for
3339:all
3305:<
3294:for
3180:1.74
3161:-SAT
3101:and
3062:-bit
2292:-SUM
2105:one.
1872:>
1837:>
1826:any
1824:for
1808:>
1786:-SAT
1763:-CNF
1700:-CNF
1638:-CNF
1617:any
1600:>
1275:The
824:The
809:<
635:-SAT
505:-SAT
422:-SAT
307:-SAT
188:-SAT
167:The
97:>
4643:gap
4633:gap
4460:doi
4415:doi
4364:doi
4318:doi
4244:doi
4203:doi
4172:doi
4079:doi
4034:doi
3990:doi
3954:doi
3883:doi
3823:doi
3455:log
3163:in
2897:is
2796:is
2714:is
2631:is
2554:OPT
2482:OPT
2247:in
2193:on
2116:SNP
2089:CNF
1991:CNF
1962:CNF
1949:to
1790:if
1406:as
1238:lim
862:is
771:log
208:ors
206:of
204:and
198:in
19:In
4702::
4466:,
4431:,
4421:,
4413:,
4378:,
4372:MR
4370:,
4362:,
4350:45
4348:,
4324:,
4316:,
4260:,
4250:,
4242:,
4199:72
4197:,
4185:^
4166:,
4135:;
4122:^
4095:,
4085:,
4077:,
4045:^
4032:,
4020:63
4018:,
4001:^
3988:,
3952:,
3902:^
3889:,
3839:,
3829:,
3806:^
2185:,
2181:,
812:1.
43:,
4645:)
4641:(
4635:)
4631:(
4504:e
4497:t
4490:v
4462::
4417::
4366::
4356::
4320::
4310::
4246::
4236::
4205::
4174::
4168:1
4081::
4036::
3992::
3956::
3885::
3865:k
3825::
3763:A
3739:A
3719:A
3701:,
3689:f
3667:)
3664:n
3661:(
3658:f
3654:/
3648:n
3644:2
3623:A
3593:1
3587:i
3567:]
3564:i
3561:[
3556:W
3548:]
3545:i
3542:[
3537:M
3506:k
3482:n
3461:n
3452:k
3438:;
3426:]
3423:1
3420:+
3417:i
3414:[
3409:M
3401:]
3398:i
3395:[
3390:W
3382:]
3379:i
3376:[
3371:M
3359:,
3347:i
3331:.
3320:,
3308:1
3302:c
3281:)
3274:c
3270:n
3265:2
3261:(
3258:O
3224:,
3212:k
3189:)
3184:n
3176:(
3173:O
3149:k
3124:)
3121:m
3118:(
3115:o
3111:2
3087:)
3084:m
3081:(
3078:o
3050:m
3027:]
3024:m
3021:,
3018:1
3015:[
2972:.
2958:)
2955:1
2952:(
2949:O
2945:n
2939:w
2933:)
2927:)
2924:1
2921:(
2918:o
2912:k
2907:(
2882:k
2871:,
2857:)
2854:1
2851:(
2848:O
2844:n
2838:w
2832:)
2826:)
2823:1
2820:(
2817:o
2811:2
2806:(
2789:,
2775:)
2772:1
2769:(
2766:O
2762:n
2756:w
2750:)
2744:)
2741:1
2738:(
2735:o
2729:3
2724:(
2706:,
2692:)
2689:1
2686:(
2683:O
2679:n
2673:w
2667:)
2661:)
2658:1
2655:(
2652:o
2646:2
2641:(
2617:w
2595:.
2583:)
2578:)
2575:1
2572:(
2569:O
2565:n
2559:)
2549:(
2546:O
2542:2
2538:(
2535:O
2523:.
2511:)
2506:)
2503:1
2500:(
2497:O
2493:n
2487:)
2477:(
2474:o
2470:2
2466:(
2463:O
2441:.
2427:)
2424:1
2421:(
2418:o
2412:k
2408:n
2383:k
2372:.
2358:)
2355:k
2352:(
2349:o
2345:n
2322:k
2302:n
2290:k
2285:.
2271:)
2268:k
2265:(
2262:o
2258:n
2235:k
2202:n
2173:k
2167:.
2155:c
2131:n
2127:c
2085:s
2066:.
2054:)
2049:n
2042:2
2038:(
2035:O
1987:s
1976:,
1958:s
1933:k
1929:s
1902:s
1875:0
1867:3
1863:s
1852:,
1840:0
1834:k
1811:0
1803:k
1799:s
1774:k
1751:k
1730:)
1725:n
1718:2
1714:(
1711:O
1688:k
1667:)
1662:n
1655:2
1651:(
1648:O
1626:k
1615:,
1603:0
1579:.
1565:1
1562:+
1559:k
1555:s
1530:k
1526:s
1505:k
1495:.
1483:)
1480:k
1476:/
1466:1
1463:(
1454:s
1445:k
1441:s
1404::
1392:k
1364:s
1341:k
1337:s
1314:.
1302:1
1299:=
1290:s
1263:.
1258:k
1254:s
1242:k
1234:=
1225:s
1197:,
1192:4
1188:s
1184:,
1179:3
1175:s
1162:.
1148:)
1145:n
1142:(
1139:o
1135:2
1114:.
1100:)
1097:n
1094:(
1091:o
1087:2
1062:3
1058:s
1034:i
1009:)
1004:n
999:i
990:2
986:(
983:O
961:3
957:s
946:,
932:)
929:n
926:(
923:o
919:2
906:.
892:)
889:n
886:(
883:o
879:2
860:,
846:3
842:s
805:)
799:k
796:2
788:2
784:(
775:2
762:k
758:s
747:,
727:4
723:s
714:3
710:s
688:k
678:.
666:)
661:n
654:2
650:(
647:O
623:k
576:k
572:s
561:.
547:)
544:n
541:(
538:o
535:+
532:n
527:k
523:s
518:2
493:k
470:k
466:s
455:,
443:3
437:k
410:k
389:n
369:,
364:)
361:1
358:(
355:O
351:n
345:n
340:)
334:k
331:2
323:2
319:(
295:k
270:k
246:k
218:k
176:k
140:.
135:n
130:3
126:s
121:2
100:0
92:3
88:s
65:)
62:n
59:(
56:o
52:2
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.