CDR: Re: Minesweeper and defeating modern encryption technology

[Jim Choate]

On Sat, 4 Nov 2000, dmolnar wrote:

> I'm sorry - by the definitions I know, Declan has it closer.
> I'm not sure what you're getting at with "any time that can't be
> described..." or "something that executes in factorial or exponential
> time." As far as I know, NP is a class of *problems*, not a
> class of running times or even a class of algorithms.

Actualy it's all of them. Where the question comes from is when one looks
at what it different instances of a given problem (e.g. the number of
closed loop paths with no double crossings of a set of bridges, or the
number of sequences that a set of cities can be visited without repeats).

The goal is to find a solution in a fewer number of steps. There seem to
be two major categories P and NP.

So for the travelling salesman problem the question becomes how to
describe the way the resources and problem space grow with relation to the
number of cities. Were that relation to be describable in a polynomial
then it would be a P. It looks like the problem is not describable by a
polynomial and is therefore NP.

> It doesn't make sense to say "x^2 is in NP", strictly speaking. 

Stripping context removes meaning for anything. It's also changing the
rules in the middle of the game.

Well, if we're going to speak strictly then you're wrong. Strictly
speaking we're talking of the relative complexity to resolve certain
classes of problems. And in that case it DOES make sense to word
statements like this.

One can say that a given problem is "x^2" (which can't be NP since x^2 is
a monomial, a class of polynomial and therefore P) with relation to
resources or number of potential solutions with respect to going from n to
n+1.

So, if I have 10 of something and manipulate them and it takes me x amount
of time and y resources. And I know the problem is "x^2" then I know that
even small changes will drasticaly increase the number of solutions that I
have to resolve. In fact I know that if I go to 20 of them things then
I'll have to deal with a run time of approx. x^2 and require about y^2
resources.

The point is to find an algorithm that uses those resources more
sparingly.

> It doesn't make sense to say "Ford-Fulkerson is in NP", strictly speaking. 

It depends on it's complexity. And it does make sense of speaking to a
particular algorithm (e.g. Seive of Aritoshanese) as being NP (which it
is).

> It makes more sense to say "primality testing" is in NP, if that
> refers to the problem of "Given a number n, is n prime?" 

No, because 'primality testing' has a host of algorithms. It appears they
are NP, but if somebody were to find a NEW algorithm that did it in P then
primality testing, at least with respect to that algorithm, would be a P
class problem.

Another aspect of the N=NP is that the assumption is that if we can
resolve a single NP to a P then that should resolve ALL NP to P. That's a
pretty big leap with no real analysis behind it. A canon of faith rather
than proof or fact.

So the question does in fact effect isues of problem class, algorithm
selection, and execution resource requirement.
 
    ____________________________________________________________________

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