# Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests?

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?

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