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