Since you are free to chose any formula for the SAT problem, doesn't the choice of a formula that requires a test for each subset of the group of variables force it to perform $2^N$, essentially making SAT unsolvable in polynomial time in respect to the number of variables on the input?

  • $\begingroup$ not stated very clearly. anyway its conjectured but an open problem to prove lower bounds for this/ area. P=?NP $\endgroup$
    – vzn
    Nov 4, 2014 at 18:26

1 Answer 1


When talking about the complexity of SAT, we usually care only about the complexity in terms of input size. This is because the classes P and NP are defined this way: they are oblivious to what the input represents. Your formula, while depending on a small number of variables, will be very long.

3SAT is nicer in this regard, since assuming clauses don't repeat and every variable appears at least once, the number of variables, the number of clauses, and the bitlength of the input are all polynomially related, so from the point of view of complexity theory, any of them could serve as the parameter against which complexity is measured.

Moreover, I don't see why any particular choice of formula would "require a test for each subset of the group of variables". We don't know how to substantiate claims of this sort in the case of SAT.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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