Talk:CNF Satisfiability Problem is NP-Complete

We've already got a page describing how a boolean expression can be turned into CNF (and DNF and NNF come to that). We want to link to it rather than reinvent it all. --prime mover 00:18, 2 June 2011 (CDT)

I took a quick look. It is true that people have already established that any statement can be converted into CNF. However, one of the key elements in showing that CNF SAT is NP-complete is showing how SAT is polynomially reducible to CNF. If someone used the conversion scheme implied by the proofs as an algorithm they would end up with an exponential explosion on some problems. The other conversion schemes preserve logical equivalence where my only concerns is preserving satisfiability and restricting the time and space of the calculation and the output. The two schemes have different goals and imply different algorithms. In that light, I think listing them both is appropriate. In any case, thank you for pointing that out.--Emichael 00:55, 2 June 2011 (CDT)

Better approach would be to merge the work. Put the algorithms you are documenting into the original page, which will enhance both approaches. Perhaps. --prime mover 01:15, 2 June 2011 (CDT)