Is SAT in P if there are exponentially many clauses in the number of variables?

Question

I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.

I'd like to know why $\text{Long-SAT} \in P$. First I thought it is $\text{NPC}$ since I can do a polynomial-time reduction from $\text{SAT}$ to $\text{Long-SAT}$, no?

But maybe I can reduce $\text{2-SAT}$ to $\text{Long-SAT}$? How do I do that?

Answer 1

Unless I'm missing something, it's trivially in P as the length of the formula is exponential in the number of variables. Hence all $2^{n}$ truth assignments can be generated and checked in polynomial time in the length of the formula.

Answer 2

In this case, the answer is trivial as Luke points out. However, as you seem to have come up with the definition yourself, note this.

For SAT, so-called phase transitions regarding the ratio of variable count to clause count have been observed [1,2]. If it is small, instances are easy, and hard if it is large. There seems to be a more or less sharp transition from easy to hard. This seems to be an active area of research. cstheory.SE has some more on this phenomenon.

So, if you adjust your definition of "long" to polynomial blowup, you might indeed get an non-trivially easy class -- that is, in P -- just because you have much more clauses than variables.

---

1. The SAT Phase Transition by I. P. Gent (1994)
2. Determining computational complexity from characteristic 'phase transitions' by R. Monasson, R. Zecchina et al. (1999)