CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

On Sat, 4 Nov 2000, dmolnar wrote:

> On Sat, 4 Nov 2000, Jim Choate wrote:
> 
> > You are in fact saying if I can resolve one NP -> P then I can resovle ALL
> > NP as P. Yet in your earlier email you said the opposite, that you didn't
> > believe that saying the solution of one NP in a P format meant that all NP
> > could be solved in a P format.
> 
> I was trying to make a distinction between two kinds of problems. 
> I'm sorry if I wasn't clear.
> 
> 1) The first kind are NP-hard problems. These are problems for which
> knowing an algorithm to solve the problem *would* allow you to solve
> every problem in NP. These are the kinds of problems I was referring
> to in the paragraph I snipped from this message.

Let's start with a set of sentences. Each of those sentences is a sequence
of connective, operators, and values that reduce to binary values. Our
job is to determine the truth or falsity value of each sentence in that
set. I further see no reason to suspect that the sentence set itself is
even countable (and even if it is it is still infinite in extent).

What you propose isn't possible. There are logical statements in the P
& NP class which are not provable. There is no way that you can say that a
set of sentences can at the same time contain insoluble members (and there
isn't a way to tell them apart since the test may itself be unprovable)
and have an algorithm which will solve all of them because you can solve
one of them.

Now if you restrict the problems to specific domains (since NP contains P
I'll talk only to NP) then we are injecting a distinction of class in
the NP and there goes our "if I can prove one of them I can prove all of
them".

    ____________________________________________________________________

                     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 --'-
    --------------------------------------------------------------------