Cook-Levin and I

My hit at NP-completeness kept me thinking on those lines. Today, I was reading Cook-Levin Theorem in the bus on my way to work. It actually simplifies. Rather, it atleast simplifies my understanding of the problem instead of those esoterics of polynomial time non-deterministic algorithm (clumsy English :().

An expression is satisfiable iff there is some assignment of truth values to the variables that makes the entire expression true.

I am getting more and more convinced that this is a 'doable' problem. Boolean satisfiability problem is the problem of determining if the variables in a given boolean formula can be assigned in such a way as to make the formula evalue to TRUE. I think there are two ways of approaching this problem - one to 'satisfy' it and simultaneously try to 'negate' it. Negation is a common method in theorem proving. You make an assumption and proceeding further on it arrive at a contradiction, thus negating the assumption. Boolean formulae are in two mutually convertible forms - sop (sum of products) and pos (product of sum). For example,

A'B'C+A'BC+ABC'+ABC=(A'+B'+C')(A'+B+C')(A'+B+C)(A+B'+C)

I think now we should try to prove AND negate to arrive at the solution. Prove using sop and negate using equivalent pos. Taking sop, it is obvious that in boolean addition, even one term (say A'B'C) evaluating to TRUE would lead to whole boolean equation evaluating to TRUE. Similarly taking pos, it is obvious that in boolean multiplication, even one term (say A'+B'+C') evaluating to FALSE would lead to the whole boolean equation evaluating to FALSE. So A=0, B=0, C=1 would lead A'B'C=1, thereby whole equation to 1. Similarly A=1,B=1,C=1 would lead A'+B'+C'=0+0+0=0. Use sop to prove and pos to negate. What is the 'issue' here (in getting the million $)? ;)

Wonder what/where the catch is :o