HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How does SETH implies ETH?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
ethhowimpliesdoesseth

Problem

I know that ETH states that 3-SAT is not solvable in $2^{o(n)}$ time, the best known bound for 3-SAT is around $O(2^{.38n})$. Whereas, SETH states that there is no universal $\delta$ such that for every positive integer $k$, a $k$-SAT problem is solvable in $O(2^{\delta n})$ time.

It is not clear to me that how does SETH is stronger, and SETH implies ETH.

Thanks

Solution

The more usual (and slightly stronger) formulation of the exponential time hypothesis is that there is $\epsilon > 0$ such that solving 3SAT requires time $\Omega(2^{\epsilon n})$ (see, for example, Abboud, Backurs and Williams), where $n$ is the number of variables.

The strong exponential time hypothesis states that for each $\epsilon > 0$ there exists $k\ge3$ such that solving $k$SAT requires time $\Omega(2^{(1-\epsilon)n})$ (again, see the paper mentioned above).

Showing that SETH implies ETH isn't trivial. The idea is to show that $k$SAT reduces to sparse $k$SAT, which is $k$SAT restricted to instances with $O(n)$ clauses. Such instances can be coded as 3SAT instances with $O(n)$ variables. Therefore if we can solve 3SAT in time $O(2^{\gamma n})$ for every $\gamma>0$, then we can also solve $k$SAT in time $O(2^{\gamma n})$ for every $\gamma>0$. For the details, consult Impagliazzo, Paturi and Zane, Which problems Have strongly exponential Complexity?.

Context

StackExchange Computer Science Q#84799, answer score: 6

Revisions (0)

No revisions yet.