From: Johannes H Andersen <johannes.andersen@brunel.ac.uk>
Subject: Re: NP=P
Date: Mon, 25 Dec 2000 13:31:35 -0800
Newsgroups: sci.math
Summary: [missing]

Naren Saagar wrote:
> 
> Hi
> 
> I'm a student of Comp Theory, and I badly want to know what NP=P is all
> about. I keep hearing it all the time, and my teacher mentioned it in class
> once. Where can I find material regarding this.
> 
> Please, please help.
> 
> Thank you.
> 


Lots of professionals think that NP stands for: Non-polynomial time, but
this is totally misunderstood. NP is perhaps an unfortunate name, but
then it can serve to test their knowledge or otherwise :-).

NP stands for: Non-deterministic polynomial time. If an algorithm is NP,
then it says that any randomly found trial solution can be verified to
solve the problem in polynomial time. So although it may be hard to find
a solution to the problem, you can fairly easily verify that it really
is a solution.  However, in practice, polynomial time is no guarantee 
that the problem is easy to solve, but without a polynomial time, a
problem is much more difficult to solve and you have to rely on
exhaustive searches or trial and error heuristics. 

Since a problem which has a polynomial time algorithm (P) is also
trivially verifiable in polynomial time, then it follows that any
algorithm belonging to P also belongs to NP.

A problem p may be solved by an algorithm. If the best known algorithm
is polynomial time (P), then the problem is in P. If there is no known
polynomial time algorithm for the problem, then this may be because
such an algorithm has not yet been found, the situation is not clear.
However there MAY BE an algorithm in NP which solves the problem; if
this is the case then we say that the problem is in NP. If an algorithm
in P for the problem should turn up later, then there is no contradiction
because NP (cleverly) includes P. So NP is in a sense a positive message,
there exists problems which are not even in NP. An example: TSP;
The Traveling Salesman.  

Now the crunch: IF a problem which is in NP, and IF for any problem
in NP, the problem consisting of transforming the first problem into
that problem is itself a problem in P, then the first problem is
called NP-Complete.

Another way characterisation NP-Complete problems is saying that IF
any NP-Complete problem can be solved in polynomial time, then ALL
problems in NP can be solved in polynomial time.

This is a simple, but nevertheless a working explanation. There are
much more detailed definitions of the basic algorithm steps 
involving Turing Machines and complicated explanations and theories
to go with them, but the above explanation is the essence.

The hypothesis (P=NP) essentially says that any problem which is 
polynomially verifiable is also solvable in polynomial time. This 
may or may not be true. I'm not able to judge the recent paper on
this. This is a conundrum. Even if is was true, would it be of
practical use?   

Johannes