<p>I think that your question is already solved in <a href="http://www.sciencedirect.com/science/article/pii/S0022000000917276" rel="nofollow">On the Complexity of K-SAT</a> by Russell Impagliazzo and Ramamohan Paturi.</p>

<p>And the answer, as anticipated by JeffE is yes.</p>

CC BY-SA 3.0
2011-12-16T18:07:41.933Z
2011-12-16T18:07:41.933Z
Carlos Linares López
<p>Is there a conjecture such that if the conjecture holds then the following (1) and (2) hold ?</p>

<p>(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.  </p>

<p>(2)The exponential time hypothesis</p>

<p>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.   </p>

CC BY-SA 3.0
2011-12-16T12:27:20.793Z
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
CC BY-SA 3.0
2011-12-16T13:30:25.897Z
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ε
<cc.complexity-theory><sat>
How the Number of Clauses Change the Complexity of Worst Case k-SAT ?
spring.flower
# How the Number of Clauses Change the Complexity of Worst Case k-SAT ?

(Asked by: username_0 on 2011-12-16)

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.

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: 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$.  
> **username_2**: Trivially yes: I conjecture that both conjecture (1) and conjecture (2) are true.  (That's not what you mean?  Then what do you mean?)  

---

## 1 answers

### Answer by username_3 on 2011-12-16. Score: 2

I think that your question is already solved in [On the Complexity of K-SAT](http://www.sciencedirect.com/science/article/pii/S0022000000917276) by Russell Impagliazzo and Ramamohan Paturi.

And the answer, as anticipated by JeffE is yes.


---

