Is P Equal to NP? A Conjecture on the Difficulty of Problem Solving

[Char. Limit]

P=NP?

to me, this suggests that N=1...

 

[zhermes]

it depends on what its referring to... but yeah, if 'P' & 'N' are independent variables... then N = 1...

 

[Office_Shredder]

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 x^y + y^x=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