Revision as of 13:56, 20 September 2012

Is P equal to NP?

(Quick overview from Wikipedia):

The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize for the first correct proof.

In essence, the question P = NP? asks: if 'yes'-answers to a 'yes'-or-'no'-question can be verified "quickly" (in polynomial time), can the answers themselves also be computed quickly?

--ysuo_MA375Fall2008walther

A helpful example would be to consider the subset-sum problem, an example of a problem which is "easy" to verify, but whose answer is believed (but not proven) to be "difficult" to compute. Given a set of integers, does some nonempty subset of them sum to 0? For instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0? The answer "yes, because {−2, −3, −10, 15} add up to zero", can be quickly verified with a few additions. However, finding such a subset in the first place could take much longer. The information needed to verify a positive answer is also called a certificate. Given the right certificates, "yes" answers to our problem can be verified in polynomial time, so this problem is in NP.

An answer to the P = NP question would determine whether problems like the subset-sum problem are as "easy" to compute as to verify. If it turned out P does not equal NP, it would mean that some NP problems are substantially "harder" to compute than to verify.
--Jniederh 18:18, 23 November 2008 (UTC)

One way to think about the problems being in the same situation is to think of a way to solve one problem using another problem. For example, if you could find a way to solve any Hamilton Path problem with some "subset sum" problem (using polynomial time to convert the problem), then you could show that if you could solve the "subset sum" problem in polynomial time, then you could solve the Hamilton Path in polynomial time. --Norlow 23:56, 23 November 2008 (UTC)

An example which uses the above idea is shown at the following site: Minesweeper to solve P=NP?. The author shows how the 3-SAT problem can be transformed in polynomial time into a question about the solvability of a Minesweeper board! Therefore, if you could find a general solution to any Minesweeper board in polynomial time, you would be able to solve 3-SAT (which is NP-complete) in polynomial time.

--Nathan Claus 17:27, 7 December 2008 (UTC)

In short, this problem is whether all NP-problems are actually P-problems. np is an abbreviation for nondeterministic polynomial and p is just for polynomial. the answer for this problem is not still clear, if NP and P are same, asymptotically faster algorithms may exist. in order to understand and analyze this question, academic background about algorithm complexity, decision problem, (non)deterministic algorithm, polynomial time and NP-completeness is needed. If the problem (p=np) is solved, it would be so amazing, for what ever thing the answer is. because if it is proved, very many problem that we have considered impossible to solve efficiently can be solved at a time.

--Jungil Lee 22:19, 8 December 2008 (UTC)

To understand the question and its impact, you first need to know what P and NP are. This discussion is a little imprecise, but it should give you an idea of what's involved. P is the set of problems that can be solved in deterministic polynomial time. That means for a problem with inputs of size N, there must be some way to solve the problem in F(N) steps for some polynomial F. F can be any polynomial, even N to the 10 millionth power. NP is the set of problems you can solve in non-deterministic polynomial time. That means for a problem with inputs of size N, there must be some way to solve the problem in F(N) steps for some polynomial F just as before. In NP, however, the program is allowed to make lucky guesses, though it must prove the solution is correct. The standard format for a program in NP is: 1.Guess the answer. 2.Verify that the answer is correct in polynomial time. Now that you know what P and NP are, does P = NP? No one has ever proven that they are equal and no one has ever proven they are not. A lot of smart people have spent a lot of years showing one problem is as hard as another. There is a large class of problems called NP-complete that you can show are equally difficult. For example, if you can find a deterministic polynomial solution for the Traveling Salesman problem (finding the shortest path that visits a set of cities and returns to the start), you can also find one for the SAT problem (find an assignment of values to Boolean variables in a logical statement to make it true). Despite all efforts, however, no one has ever shown that an NP-complete problem is also in P. Because no one has found such an example, many researchers believe that P <> NP.

--Kim297 23:13, 7 December 2008 (UTC)

Back to MA375, Fall 2008, Prof. Walther