Strong Exponential Time Hypothesis (SETH)
- 1 Target Problem
- 2 Description
- 3 Implies the following Hypothesis
- 4 Implied by the following Hypothesis
- 5 Computation Model
- 8 References/Citation
Target Problem
Description.
For every $\epsilon > 0$, there exists an integer $k \geq 3$ such that $k$-SAT cannot be solved in $O(2^{(1-\epsilon) n})$ time.
Implies the following Hypothesis
MBETH , ETH
Implied by the following Hypothesis
Computation model.
Word-RAM on $\log(n)$ bit words
References/Citation
Impagliazzo, Paturi, and Zane
Navigation menu
Exact Algorithms and Strong Exponential Time Hypothesis
- Reference work entry
- First Online: 01 January 2016
- Cite this reference work entry
- Joshua R. Wang 2 &
- Ryan Williams 3
82 Accesses
1 Citations
Years and Authors of Summarized Original Work
2010; Păatraşscu, Williams
2011; Lokshtanov, Marx, Saurabh
2012; Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlström
Problem Definition
All problems in NP can be exactly solved in 2 poly( n ) time via exhaustive search, but research has yielded faster exponential-time algorithms for many NP-hard problems. However, some key problems have not seen improved algorithms, and problems with improvements seem to converge toward O ( C n ) for some unknown constant C > 1.
The satisfiability problem for Boolean formulas in conjunctive normal form, CNF-SAT, is a central problem that has resisted significant improvements. The complexity of CNF-SAT and its special case k -SAT, where each clause has k literals, is the canonical starting point for the development of NP-completeness theory.
Similarly, in the last 20 years, two hypotheses have emerged as powerful starting points for understanding exponential-time complexity. In 1999,...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Durable hardcover edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Recommended Reading
Calabro C, Impagliazzo R, Paturi R (2009) The complexity of satisfiability of small depth circuits. In: Chen J, Fomin F (eds) Parameterized and exact computation. Lecture notes in computer science, vol 5917. Springer, Berlin/Heidelberg, pp 75–85. doi:10.1007/978-3-642-11269-0_6. http://dx.doi.org/10.1007/978-3-642-11269-0_6
Chen J, Chor B, Fellows M, Huang X, Juedes D, Kanj IA, Xia G (2005) Tight lower bounds for certain parameterized np-hard problems. Inf Comput 201(2):216–231. doi:http://dx.doi.org/10.1016/j.ic.2005.05.001. http://www.sciencedirect.com/science/article/pii/S0890540105000763
Cygan M, Dell H, Lokshtanov D, Marx D, Nederlof J, Okamoto Y, Paturi R, Saurabh S, Wahlstrom M (2012) On problems as hard as cnf-sat. In: Proceedings of the 2012 IEEE conference on computational complexity (CCC ’12), Washington, DC. IEEE Computer Society, pp 74–84. doi:10.1109/CCC.2012.36. http://dx.doi.org/10.1109/CCC.2012.36
Fomin F, Kratsch D (2010) Exact exponential algorithms. Texts in theoretical computer science, an EATCS series. Springer, Berlin/Heidelberg
Google Scholar
Impagliazzo R, Paturi R (2001) On the complexity of k-sat. J Comput Syst Sci 62(2):367–375. doi:http://dx.doi.org/10.1006/jcss.2000.1727. http://www.sciencedirect.com/science/article/pii/S0022000000917276
Impagliazzo R, Paturi R, Zane F (2001) Which problems have strongly exponential complexity? J Comput Syst Sci 63(4):512–530. doi:http://dx.doi.org/10.1006/jcss.2001.1774. http://www.sciencedirect.com/science/article/pii/S002200000191774X
Lokshtanov D, Marx D, Saurabh S (2011) Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the twenty-second Annual ACM-SIAM symposium on discrete algorithms (SODA ’11), San Francisco. SIAM, pp 777–789. http://dl.acm.org/citation.cfm?id=2133036.2133097
Chapter Google Scholar
Pătraşcu M, Williams R (2010) On the possibility of faster sat algorithms. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms (SODA ’10), Philadelphia. Society for Industrial and Applied Mathematics, pp 1065–1075. http://dl.acm.org/citation.cfm?id=1873601.1873687
Woeginger G (2003) Exact algorithms for np-hard problems: a survey. In: Jünger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization Eureka, you shrink! Lecture notes in computer science, vol 2570. Springer, Berlin/Heidelberg, pp 185–207. doi:10.1007/3-540-36478-1_17. http://dx.doi.org/10.1007/3-540-36478-1_17
Download references
Author information
Authors and affiliations.
Department of Computer Science, Stanford University, Stanford, CA, USA
Joshua R. Wang
Ryan Williams
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Joshua R. Wang .
Editor information
Editors and affiliations.
Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL, USA
Ming-Yang Kao
Rights and permissions
Reprints and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry.
Wang, J.R., Williams, R. (2016). Exact Algorithms and Strong Exponential Time Hypothesis. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_519
Download citation
DOI : https://doi.org/10.1007/978-1-4939-2864-4_519
Published : 22 April 2016
Publisher Name : Springer, New York, NY
Print ISBN : 978-1-4939-2863-7
Online ISBN : 978-1-4939-2864-4
eBook Packages : Computer Science Reference Module Computer Science and Engineering
Share this entry
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
IMAGES
VIDEO