## 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

95 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

- Get 10 units per month
- Download Article/Chapter or Ebook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- 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

## 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

Help | Advanced Search

## Quantum Physics

Title: the quantum strong exponential-time hypothesis.

Abstract: The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability with a speedup over exhaustive search. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are hard to find. In this work, we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to SETH. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in BQP. As an example, we illustrate the use of the QSETH by providing a conditional quantum time lower bound of $\Omega(n^{1.5})$ for the Edit Distance problem. We also show that the $n^2$ SETH-based lower bound for a recent scheme for Proofs of Useful Work, based on the Orthogonal Vectors problem holds for quantum computation assuming QSETH, maintaining a quadratic gap between verifier and prover.

Comments: | changes: updated grant information |

Subjects: | Quantum Physics (quant-ph); Computational Complexity (cs.CC) |

Cite as: | [quant-ph] |

(or [quant-ph] for this version) | |

Focus to learn more arXiv-issued DOI via DataCite |

## Submission history

Access paper:.

- Other Formats

## References & Citations

- INSPIRE HEP
- Google Scholar
- Semantic Scholar

## BibTeX formatted citation

## Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

- Institution

## arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

- DSpace@MIT Home
- MIT Open Access Articles

## Results on a Super Strong Exponential Time Hypothesis

## Publisher Policy

Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.

## Terms of use

Date issued, collections.

Show Statistical Information

## Chi's math corner

A collection of what I'm reading or interested in

- Basics of Quantum Computing
- Hamiltonian Simulation
- Adiabatic Quantum Computing

## Hardness of Easy Problems

- Orthogonal Vector Problem
- Complexity Theory
- Other musings

## “Hardness of Easy Problems”

A not-so-easy puzzle waiting to be solved.

I started exploring the subject by reading this survey paper: Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Virginia V. Williams)

http://theory.stanford.edu/~virgi/ipec-survey.pdf

i) They are “reducible” to many other problems, so solving them faster means that we can solve many other problems faster

ii) They are “reducible” to an NP problem, so a subcubic algorithm leads to a sub-exponential algorithm in solving SAT (or other NP problem).

The notion of “reducible” in the above two statements is different from the usual NP-reducible sense.

What about “reducible”? Now we need to learn the notion of a “tight reduction”, or “fine-grained reduction”, as clarified by Williams in her survey paper above:

The paper offers a comprehensive relations among some famous problems (Orthogonal Vectors (OV), All-Pairs Shortest Path (APSP), Hitting Set (HS), k-SAT) and some examples of the reductions involved.

(Digression: Have you wondered why these two researchers share the same last name? I did; so I googled them and found out that they wrote a joint paper while visiting the same university, and now they’re married and both are working at Stanford. What a love story!)

I spent a lot of time developing a less-brute-force algorithm for OV, which I will elaborate in another entry.

So, ready to delve into some more research papers?

1)Subcubic Equivalences Between Path, Matrix, and Triangle Problems (Virginia Vassilevska Williams, Ryan Williams) : http://web.stanford.edu/~rrwill/tria-mmult.pdf

2) Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter (Amir Abboud, Fabrizio Grandoni, Virginia Vassilevska Williams)

This paper also demonstrates the reduction technique between graph problems. I tried imitating the technique to draw an arrow that they couldn’t draw in this paper, and failed. It seems like I haven’t reached a new insight to reduce diameter problem to any of the problems in the Radius/Betweeness Centrality/Negative Triangle group.

Latest result (and fastest so far) on negative-weight shortest paths problem.

4) Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs (Liam Roditty & Virginia Vassilevska Williams)

[This entry is dedicated to Veena, whose curiosity and love for learning have motivated me to write this post.]

- Export ACM-XML
- Export DOAJ-XML
- Export Schema.org
- Export BibTeX

## Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)

Author virginia vassilevska williams.

- Part of: Volume: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs) Part of: Conference: International Symposium on Parameterized and Exact Computation (IPEC)

- Publication Date: 2015-11-19

- Filesize: 488 kB

## Document Identifiers

- DOI: 10.4230/LIPIcs.IPEC.2015.17
- URN: urn:nbn:de:0030-drops-55683

## Author Details

Cite as get bibtex.

- satisfiability
- strong exponential time hypothesis
- shortest paths
- equivalences
- fine-grained complexity
- Access Statistics
- Total Accesses (updated on a weekly basis) 0 PDF Downloads 0 Metadata Views

Feedback for Dagstuhl Publishing

## Thanks for your feedback!

Could not send message.

## Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

## Different definitions of Exponential Time Hypothesis

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it:

Statement 1 There exists no $2^{o(n)}$ algorithm for $3$ -SAT, where $n$ is the number of variables.

Statement 2 If $\delta_q$ ( $q \ge 3$ ) is the infimum of set of constants $c$ for which there exists an algorithm for solving $q$ -SAT (each clause has $\le q$ literals) in time $\mathcal{O}^{\text{*}}(2^{cn})$ (here $\mathcal{O}^{\text{*}}(.)$ supresses any non-exponential part of the running time). Then $\delta_q > 0$ .

I can see that if $1$ holds, then so does $2$ . But why is it so that $2$ may/may not imply $1$ ? If $2$ holds then would it be wrong to argue that $\delta_3 > 0$ . And as $\delta_{i+1} \ge\delta_i$ ( $i \ge 3$ ), because increasing upper bound on number of literals in each clause can only make the problem more difficult to solve, it will imply $1$ .

- complexity-theory
- time-complexity
- satisfiability

- $\begingroup$ Strong ETH states that $\delta_q \to 1$. $\endgroup$ – Yuval Filmus Commented Dec 5, 2020 at 11:46
- $\begingroup$ Also, the sequence $\delta_q$ is (possibly weakly) increasing . If you can solve $(k+1)$-SAT, then you can use the same algorithm to solve $k$-SAT using a single new dummy variable. $\endgroup$ – Yuval Filmus Commented Dec 5, 2020 at 11:47
- $\begingroup$ Sorry for the confusion, I changed the wording. The two statements for ETH are mentioned here en.wikipedia.org/wiki/Exponential_time_hypothesis (have added same link in question as well) $\endgroup$ – advocateofnone Commented Dec 5, 2020 at 11:54
- 1 $\begingroup$ Wikipedia mentions an explanation as well as a relevant citation. Have you consulted Flum & Grohe (2006)? $\endgroup$ – Yuval Filmus Commented Dec 5, 2020 at 12:28

## Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer, sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

## Browse other questions tagged algorithms complexity-theory time-complexity satisfiability or ask your own question .

- Featured on Meta
- Upcoming sign-up experiments related to tags

## Hot Network Questions

- Is there any legal justification for content on the web without an explicit licence being freeware?
- Surjective, closed local homeomorphism with finite fibers is a covering map?
- Do I need to indicate 'solo' for wind/brass instruments in shared staff?
- What was the first game to intentionally use letterboxing to indicate a cutscene?
- Can a directed set be empty?
- Is there any other reason to stockpile minerals aside preparing for war?
- White grids appears when export GraphicsRow to PDF
- DSP Puzzle: Advanced Signal Forensics
- Why potential energy is not considered in the internal energy of diatomic molecules?
- Can my IP be found on Telegram by malicious people?
- Do IDE data lines need pull-up resistors?
- Correlation for Small Dataset?
- Old book about a man who finds an abandoned house with a portal to another world
- How to Pick Out Strings of a Specified Length
- What is the translation of misgendering in French?
- Next date in the future such that all 8 digits of MM/DD/YYYY are all different and the product of MM, DD and YY is equal to YYYY
- How do you say "living being" in Classical Latin?
- How can a landlord receive rent in cash using western union
- What distinguishes boosts from general Lorentz transformations?
- Is there an image viewer for ubuntu that will read/apply xmp sidecars?
- How can I confirm for sure that a CVE has been mitigated on a RHEL system?
- Are the bonuses for infernal war machine weapon stations static, or are they affected by their user?
- Why depreciation is considered a cost to own a car?
- Are both vocal cord and vocal chord correct?

## Senior Scientist Venkat Guruswami Wins Best Paper Award at STOC 2024

Simons Institute Senior Scientist Venkatesan Guruswami, along with Bingkai Lin, Yican Sun, and Berkeley theory graduate students Xuandi Ren and Kewen Wu, received a best paper award at the 56th ACM Symposium on Theory of Computing ( STOC 2024 ) conference, for their paper, " Parameterized Inapproximability Hypothesis under ETH ." STOC is one of the two annual flagship conferences in the theory of computing, along with the IEEE Symposium on Foundations of Computer Science (FOCS). An abstract of the paper is provided below.

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this paper, Guruswami et al. prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. The authors identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

## Related stories

Appreciation and memories of Jim Simons (1938–2024), from the Simons Institute community. Featuring contributions...

We are heartbroken by the loss of Luca Trevisan, who served as senior scientist at the Institute from 2014 to 2019.

## IMAGES

## VIDEO

## COMMENTS

Exponential Time Hypothesis (ETH) and a stronger version called the Strong Exponential Time Hypothesis (SETH). Informally, ETH says that 3-SAT cannot be solved in 2 ( ) time, and SETH says that -SAT needs roughly 2 time for large . We will discuss the connections between ETH and SETH and

The exponential time hypothesis is a conjecture that satisfiability of 3-CNF formulas cannot be solved in subexponential time. It implies many other hardness results and is related to the strong exponential time hypothesis, which conjectures that the smallest number is nonzero.

Learn about the conjecture that k-SAT requires time 2(n) for some k, and its implications for other NP-complete problems and polynomial-time problems. See proofs, reductions, and examples of algorithms and lower bounds for SAT and related problems.

A talk by Ryan Williams on the Strong Exponential Time Hypothesis (SETH), a conjecture that SAT and k-SAT require exponential time. He discusses some implications, counterexamples, and related problems of SETH and its variants.

This web page explains the Exponential Time Hypothesis (ETH) and its implications for various problems in computational complexity. It also introduces the Strong Exponential Time Hypothesis (SETH) and its relation to the ETH.

Ryan Williams (MIT) presents a talk on how SETH has been used to prove conditional hardness and fine-grained complexity of many problems. Watch the video recording of the talk from Feb. 18, 2021.

2.1 Strong Exponential Time Hypothesis There is a stronger version of ETH that deals with CNF-SAT formulas rather than 3SAT. In particular, the strong exponential time hypothesis (strong ETH) says that there exists no O((2 )n)-time algorithms for CNF-SAT for any . In other words, as k!1, the constant (2 ) for k-SAT

The Strong Exponential Time Hypothesis Daniel Lokshtnaov . Tight lower bounds Have seen that ETH can give tight lower bounds How tight? ETH «ignores» constants in exponent How to distinguish 1.85n from 1.0001n? SAT Input: Formula 𝜓 with m clauses over n boolean variables.

This article surveys some of the tight lower bounds for exact algorithms that are conditional on the strong exponential time hypothesis (SETH), which asserts that k-SAT cannot be solved in O ( (2 − ε) n ) time for any ε > 0. The article gives reductions from k-SAT to other problems such as k-Dominating Set, 2Sat+2Clauses, HornSat+kClauses, and 3-Party Set Disjointness.

The authors introduce a quantum analogue of the strong exponential-time hypothesis (SETH) and show how it can be used to prove conditional quantum time lower bounds for problems in BQP. They also discuss the implications of QSETH for fine-grained complexity and quantum proofs of useful work.

SETH is a conjecture that states that k-SAT cannot be solved in subexponential time. It implies and is implied by other complexity hypotheses such as MBETH, ETH, OVH, and UOVH.

The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower ...

unifying hypothesis, thereby improving our understanding and simplifying the state of knowledge. For example, it would be nice to show that the 3-sum conjecture follows from SETH (Strong Exponential Time Hypothesis). It would also be nice to show that SETH implies that hittingset and maxflow require superlinear time. Can we prove that

Keywords and phrases reductions, satisﬁability, strong exponential time hypothesis, shortest paths, 3SUM, equivalences, ﬁne-grained complexity Digital Object Identiﬁer 10.4230/LIPIcs.IPEC.2015.16 1 Introduction The core goal of algorithmic research is to determine how fast computational problems can be solved in the worst case.

A quantum analogue of the SETH conjecture, which states that CNF formulas cannot be analyzed faster than exhaustive search. The authors use QSETH to translate quantum query lower bounds to conditional quantum time lower bounds for problems in BQP.

the improvement in the time complexity does not seem possible, as discussed above. This motivated the formulation of a stronger conjecture { Strong ETH (SETH). Conjecture 2 (SETH: Strong Exponential Time Hypothesis). For every >0 there exists a ksuch that k-SAT can't be solved in time less than O(2(1 )n) , that is s 1= 1. It also

The strong exponential time hypothesis says that limk→∞sk = 1 lim k → ∞ s k = 1. I have two questions here: What if the input size is very large, say, m = Θ(3n) m = Θ ( 3 n)? Simply reading the input formula needs ω(2n) ω ( 2 n) time. In this case, limk→∞sk lim k → ∞ s k would be larger than 1 1. A paper in SAT Conference ...

> Strong Exponential-Time Hypothesis (SETH): ... Exponential-Time Hypothesis > ETH: "Exponential" P ≠ NP > Randomized Exponential-Time Hypothesis (rETH): There exist ε>0 and c>1 such that 3-SAT on n vars and c⋅n clauses can't be decided in randomized time 2ε⋅n [DHMTM'14]

This hypothesis has been called the "Super-Strong Exponential Time Hypothesis" (Super Strong ETH), modeled after the ETH and the Strong ETH. We prove two results concerning the Super-Strong ETH:1. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the "critical threshold", where the clause-to ...

Exponential Time Hypothesis Daniel Lokshtanov Dániel Marxy Saket Saurabhz Abstract ... Hypothesis (ETH) and the stronger variant, the Strong Exponential Time Hypothesis (SETH). These complexity assumptions state lower bounds on how fast satisﬁability problems can be solved. These assumptions can be

This reduction makes the OV worth exploring because the Strong Exponential Time Hypothesis (SETH): Conjecture: SETH: "For every > 0, there exists an integer k, such that Satisfiability on k-CNF formulas on n variables cannot be solved in time in expectation".

In this abstract we outline the approach, give some examples of hardness results based on the Strong Exponential Time Hypothesis, and present an overview of some of the recent work on the topic. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it: Statement 1. There exists no 2o ( n) algorithm for 3 -SAT, where n is the number of variables. Statement 2. If δq ( q ≥ 3) is the infimum of set of constants c for which there exists an algorithm for solving q -SAT (each clause has ≤ q literals) in ...

However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this paper, Guruswami et al. prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. The authors identify an ETH-hard CSP whose variables take vector values, and constraints are either ...