CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

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 at ssz.com
       www.ssz.com            .',  ||||    `/( e\      512-451-7087
                           -====~~mm-'`-```-mm --'-
    --------------------------------------------------------------------