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

  • Context: Graduate 
  • Thread starter Thread starter Char. Limit
  • Start date Start date
  • Tags Tags
    Mean
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
2 replies · 2K views
Char. Limit
Gold Member
Messages
1,222
Reaction score
23
P=NP?

to me, this suggests that N=1...
 
Mathematics news on Phys.org
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