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.

Improve this question
$\endgroup$
2
  • 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, 2011 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, 2011 at 13:30

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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