# How the Number of Clauses Change the Complexity of Worst Case k-SAT ?

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.

• 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$. – David Harris Dec 16 '11 at 12:27
• Trivially yes: I conjecture that both conjecture (1) and conjecture (2) are true. (That's not what you mean? Then what do you mean?) – Jeffε Dec 16 '11 at 13:30