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

  • Level: Graduate 
  • Thread starter Char. Limit
  • Start date
  • Tags Tags
    Mean
2 replies · 2K views · last reply
Char. Limit
Gold Member
Messages
1,222
Reaction score
23
P=NP?

to me, this suggests that N=1...
 
it depends on what its referring to... but yeah, if 'P' & 'N' are independent variables... then N = 1...
 
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