A boolean SAT problem is a set of clauses, each containing a boolean literal or its negation, all "or"-ed together.

While many SAT problems can be solved quickly, the best known algorithms to solve a boolean SAT problem take exponential time (in terms of length of input or number of variables - not well read enough to know distinction) to solve.

The boolean SAT problem is NP-complete, meaning every problem in NP has a polynomial algorithm to reduce it to a boolean SAT problem.

The exponential time hypothesis says the worst-case for some problems in NP is exponential time.

If the exponential time hypothesis is true, then boolean SAT takes exponential time, in the worst case.

3-SAT is a boolean SAT problem where clauses are limited to 3 literals or their negations.

3-SAT is NP-complete.

Given n literals, there are roughly n^3 different 3-clauses one could make. (n choose 3)

This means there are roughly 2^(n^3) different 3-SAT problems.

If the exponential time hypothesis is true solving all possible 3-SAT problems takes 2^(n^3)*2^n = O(2^polynomial(n)), which is still exponential.

In other words, if the exponential time hypothesis is true, then solving a single 3-SAT problem is about as hard as solving all possible 3-SAT problems with the same variable count.

Is this logic correct?

  • $\begingroup$ This is a good question, but it might be answered more quickly on the CS theory stack exchange. $\endgroup$ May 6, 2020 at 5:21
  • $\begingroup$ I'd use Landau (Big-Oh) notation... Technically the (3-SAT) equation is $2^{2(n) \cdot 2(n-1) \cdot 2(n-2)}$ = $2^{8n^3 -24n^2 +16n}$. That's not exactly $O(2^n)$, but $O(2^{8n^3})$, which you know. As far as complexity classes are concerned, you may need a quick way (polynomial time) to prove the result, which is required to be NP-complete. Interesting question. $\endgroup$
    – Matt Groff
    May 6, 2020 at 5:26


You must log in to answer this question.

Browse other questions tagged .