| Line 22: | Line 22: | ||
In short, this problem is whether all NP-problems are actually P-problems. np is an abbreviation for nondeterministic | 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 | + | 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 | 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. | algorithm complexity, decision problem, (non)deterministic algorithm, polynomial time and NP-completeness is needed. | ||
Revision as of 18:55, 7 December 2008
(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?
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)
