Problem Detail: 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?
Asked By : Numerator
Answered By : Luke Mathieson
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2704
