Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What does it mean to say

  1. Sep 20, 2010 #1

    Char. Limit

    User Avatar
    Gold Member


    to me, this suggests that N=1...
  2. jcsd
  3. Sep 20, 2010 #2
    it depends on what its referring to.... but yeah, if 'P' & 'N' are independent variables... then N = 1.....
  4. Sep 20, 2010 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook