On Sun, 5 Nov 2000, dmolnar wrote:
OK. This seems to be a point where the definitions are a crucial issue.
Let me define the set
SAT = { B | B is a Boolean formula, and B has a satisfying assignment}
You're quite right in noticing that this set is infinite. In particular, it has all sentences of the form (P or NOT P) OR (Q or NOT Q) OR ... i.e. all tautologies ORed with themselves.
Infinite? It isn't even countable. It's of class Aleph 1, not Aleph Null. The problem is the last conditional of your definition. It's impossible even in principle to create such a universal set and define an operator to say if a particular sentence does or doesn't resolve, never mind it's actual value. Godel disallows a universal sentence consistency verifier, as distinct from a universal resolver which it also prohibits. Your conditional assumes axiomaticaly the existance of such a beast. In effect Godel says you can't have a universal translator (i.e. Translate the Boolean sentence into a 0 or 1 depending upon if it is consistent or 'has a satisfying assignment'). You are, with that conditional, in effect saying that even though Godel's Incompleteness Theorem says that I can create Boolean sentences that are not resolvable you can resolve all of them. Clearly paradoxical. I feel safer giving up 'has a satisfying assignment' over Godel's. The reality is that if you have a problem set such that all members are resolvable you are using a sub-set of the actual problem set. In other words you've found a 'distinction'. It is my assertion that there are many such 'distinctions' in the NP set that in fact mean there are different classes of NP problems which are not resolvable to one another and whose solution algorithms are completely indipendent. The first such distinction, per Godel's, is that there are some problems I can't resolve. So, why should there be only a single distinction? I can certainly think of no reason to limit it. So, unless somebody can demonstrate that NP problems break down only into solvable and unsolvable problems (which isn't possible via Godel's) I feel pretty safe that P<>NP (I'm pretty sure nobody can build a universal tester for that either). While P may be in NP, there are some NP that won't resolve to P's. I've unexpectedly run into this exact same sort of problem with Goldbach's recently. Additive Number Theory of class h=2 and degree 1 are fun! When one speaks of 'cosmological' sets (i.e. sets that contain all possible arrangements) it isn't possible even in theory to actualy resolve all of the individual members. ____________________________________________________________________ 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 --'- --------------------------------------------------------------------