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?
