View Full Version : What does it mean to say...
Char. Limit
Sep20-10, 02:17 AM
P=NP?
to me, this suggests that N=1...
zhermes
Sep20-10, 02:23 AM
it depends on what its referring to.... but yeah, if 'P' & 'N' are independent variables... then N = 1.....
Office_Shredder
Sep20-10, 02:26 AM
P=NP is referring to two sets: P is the set of problems which can be solved with a polynomial time algorithm, and NP is the set of problems which can be checked to see if the solution is correct in polynomial time, but a solution can't be found in polynomial time.
As an example for how a distinction is natural:
For example, if I asked you to find integer solutions to the equation xy + yx=145, this would be fairly difficult. But if I tell you x=3, y=4 is a solution, it's really easy to check.
It's a famous conjecture that P is NOT equal to NP: in normal language, that just because a problem is easy to check, it doesn't mean it's easy to solve. Nobody actually has a proof one way or the other though
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.