1
$\begingroup$

Is there a conjecture such that if the conjecture holds then the following (1) and (2) hold ?

(1)The worst case time complexity of k-SAT with n variables and m clauses reaches the maximum value, if m is Cn where C is a constant.

(2)The exponential time hypothesis

This question comes from a view about input size of problems. For example, an instance of 3-SAT with n variables is a 3CNF formula and the length of the formula could be O(n^3). The complexity of obvious algorithm for 3-SAT with n variables is 2^n. 2^n is strictly smaller than 2^{ O(n^3) }. The complexity is defined as the function of input size like the length of formula and the exponential function of input length is 2^{ O(n^3) } and is not 2^n. 2^n time seems to be a sub-exponential time if the statement (1) does not hold.

$\endgroup$
  • 2
    $\begingroup$ Exponential time means $O(2^{n^q})$ for $q \in \mathbf Q$. Hence $2^n = 2^{O(|\phi|^{1/3}})$ is still exponential in the formula length $\phi$. $\endgroup$ – David Harris Dec 16 '11 at 12:27
  • 2
    $\begingroup$ Trivially yes: I conjecture that both conjecture (1) and conjecture (2) are true. (That's not what you mean? Then what do you mean?) $\endgroup$ – Jeffε Dec 16 '11 at 13:30
2
$\begingroup$

I think that your question is already solved in On the Complexity of K-SAT by Russell Impagliazzo and Ramamohan Paturi.

And the answer, as anticipated by JeffE is yes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.