On Sat, 4 Nov 2000, dmolnar wrote:
The original problem for which this was shown was formula satisfiability: "given a boolean formula, does there exist an assignment to all of its variables which makes the formula evaluate to true?" If you can solve formula satisfiability in polynomial time, you can solve any NP problem in polynomial time.
Which we now know to be impossible given Godels Incompleteness Theorem, it's also a form of Turings Halting Problem. It should be worded something like: "given SOME boolean formula,..." ____________________________________________________________________ He is able who thinks he is able. Buddha The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------