Resolution on 3-SAT instance yields in polynomial many resolvents

467 Views Asked by At

A SAT instance in CNF with $n$ variables has at most $2^n$ resolvents, therefore the resolution method is not in polynomial time.

Considering a 3-SAT instance, we have at most $n^3 + n^2 + n$ many resolvents. Therefore, we can decide 3-SAT in polynomial time by resolution.

I am sure, my second statement is wrong, because otherwise we would have $P = NP$. But I can not see my mistake. Can someone bring clarification here?

1

There are 1 best solutions below

0
On

There are only that many clauses but that only gives an upper bound for the time to test a single candidate solution. There are still $2^n$ candidates to test.