P=NP (6)

1 Name: Anonymous Scientist : 2010-04-03 18:01 ID:BNvFt/JI

In layman's terms explain the meaning of the P=NP problem

2 Name: Anonymous Scientist : 2010-04-04 02:56 ID:+AAKZs88

In fact, explaining the problem to you in layman's terms is more difficult than solving the problem itself.

3 Name: Anonymous Scientist : 2010-04-04 11:29 ID:BNvFt/JI

lol dont be like that

I know its something to do with polynomial time

4 Name: wikipedia : 2010-04-04 15:11 ID:Heaven

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?

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 three additions. However, finding such a subset in the first place could take more time. 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.

The restriction to yes/no problems is unimportant; the resulting question when more complicated answers are allowed (whether FP = FNP) is equivalent.

5 Name: Anonymous Scientist : 2010-04-08 08:47 ID:pBoKOp3v

p=np when p=0 or n=1

6 Name: Anonymous Scientist : 2010-09-27 22:58 ID:Heaven

What if p=0 but n=infinity?

This thread has been closed. You cannot post in this thread any longer.