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

What makes a problem computationally NP?

  1. Jun 18, 2018 #1
    As the title says, what makes a decision problem NP complex? Is it application of the definition (as in: solvable in polynomial time by a non-deterministic Turing machine)? Also, if P does not equal NP, does it mean that NP problems can only be solved in O(exp(n)) time/steps?
     
    Last edited by a moderator: Jul 13, 2018
  2. jcsd
  3. Jun 18, 2018 #2

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Yes. If you can solve a problem in polynomial time only if a random tape is available, then it's in NP.
    deterministic
    Yes, except it is already in P. It does not mean that a single instance of a problem couldn't be solved in P, only the problem in general can't.
     
  4. Jul 12, 2018 #3
    NP is the set of decision problems where the yes answers can be verified in polynomial time. P is a subset of NP. Note that every problem with time complexity less than polynomial is also in P.

    NP may contain more than just P. This is the case if there are problems whose solutions can be verified in polynomial time, yet cannot be solved in polynomial time (that is finding the solution is more difficult than checking that it is correct ).

    The answer to the first question you asked is yes, but I think it's better to think of it the way I explained it (yes answers can be verified in polynomial time). The answer to the second is no, like I said, P is subset of NP. NP-Complete problems are those that are in NP and NP-Hard (as hard as the hardest problems in NP). Those problems, if P is not equal to NP, are not solvable in Polynomial time.
     
  5. Jul 12, 2018 #4
    But I did not claim that if P equals NP, then NP problems are solvable in Polynomial time. O(exp(n)) is exponential time and I was wondering if (given P is not equal to NP) the NP problems are only solvable in exp(n) time.
     
  6. Jul 12, 2018 #5
    If P and NP are the same set, then of course all problems in NP are in P.

    NP is a superset of all problems easily verified, this includes O(1) problems, O(n) problems etc. If NP is not P, then it just means that P is strictly a subset of NP, not all of NP (it would mean there are at least some NP problems that are not in P).
     
    Last edited: Jul 12, 2018
  7. Jul 13, 2018 #6
    What about if P is not equal to NP? Would the problems that are in NP but not in P be of exponential complexity?
     
  8. Jul 13, 2018 #7
    This article should answer the question pretty well. If P is not NP, then there are problems in-between P and NP-Complete.
    https://en.wikipedia.org/wiki/NP-intermediate
     
  9. Jul 13, 2018 #8

    stevendaryl

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, NP is its own complexity classification.

    Here's the way I understand it:

    If a problem is in P, that means that you can find a solution in polynomial time.
    If a problem is in NP but not in P, that means that you can check whether a solution is actually a solution in polynomial time, but it would take you longer than polynomial to find it.

    The distinction between checking a solution and finding one is illustrated by the 4-color problem. You have some map of countries, and you want to pick colors from the choices Red, Yellow, Blue, Green, so that no two countries that share an edge have the same color. Coming up with a choice of colors might be very difficult: You might have to try every possible combination, and that's ##4^N## possibilities, where ##N## is the number of countries. So finding a solution might be exponential. But if somebody just handed you a colored map, you could check that no countries with a shared edge are the same color in at worst ##N^2## steps (go through every possible pair of countries, see if they share a border, and then check if they are the same color).

    That might not be an example of an NP problem, though, because there might be some clever way to cut down the number of possibilities, but it shows you the idea.
     
  10. Jul 13, 2018 #9
    Thank you for your answer. So is P - NP distinction unrelated to the algorithmic complexity of a problem? It should be though, shouldn't it? Because a problem in P is solvable in polynomial time (think O(t^N)). But what about NP, if it is not equal to P?
     
  11. Jul 13, 2018 #10

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    Why that? A distinction means you have a problem, which is in NP but not in P. For being in NP you'll need an algorithm, for not being in P you'll need a proof. But be aware that the problem is unsolved for decades now, and it is notoriously hard to prove non existence. We basically have to show, that it's not our incapability, but hard by nature.
    A problem in NP means it can be solved in exponential time and verified in polynomial. A famous example is whether Boolean expressions are true for some setting of the variables or not. To test all possibilities is exponential in time, and to check whether a setting yields true or false is polynomial. We do not know a polynomial time algorithm to find a general solution, yet. So a proof NP = P is easier than a proof P ##\subsetneq## NP, because for the former we needed only a smart algorithm to solve this Boolean problem. However, one cannot prove both. Until now, nobody has found a smart algorithm, and nobody could prove, that it's impossible.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted