From: Johannes H Andersen 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