4 ms·

What does NP stand for?

by LearnerHerzog 9y ago

sythe2o0 9y ago
Nondeterministic Polynomial (time)
deleted 9y ago
[deleted]
cpburns2009 9y ago
"NP" stands for "nondeterministic polynomial time". See: https://en.wikipedia.org/wiki/NP_%28complexity%29 https://en.wikipedia.org/wiki/NP_%28complexity%29 (Not that I have the requisite knowledge to understand it).
- dclowd9901 9y ago
  I'll treat this like an interview question, and anyone can correct me if I'm wrong: My understanding of it is that it means it's impossible to predict the best solution without brute forcing all possible combinations of action... am I close there?
  - icen 9y ago
    In the worst case, it is commonly thought (this is P vs NP) that you will have to test a super-polynomial number of solutions. It doesn't have to be all of them.
    - betterunix2 9y ago
      Technically you could solve the problem testing a polynomial number of solutions after spending super-polynomial time choosing the solutions to test.
  - nothrabannosir 9y ago
    In addition to sibling correction, np means that a given answer can be verified in polynomial time (PTIME is an algorithm in O(n^k) for input size n and a certain constant k, as opposed to e.g. O(k^n)). An example would be travelling salesman (“is there a Hamiltonian path shorter than L for given graph?”) which you can easily verify given a path: does it visit every vertex, and is it shorter than L? Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. The finding part is P [edit: which is contained in NP]. P=NP would mean that if we can easily verify a solution , then we can also find it easily in the first place. P!=NP means that there are some problems which are easy to verify the solution for,but hard to find a solution for.
    - kevinwang 9y ago
      > Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. Because nitpicking is fun, I'll add my contribution and say that the traditional definition of NP is actually about the finding of solutions, and is the etymology of the phrase "non deterministic polynomial time". That is, a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time. Of course, since our non deterministic algorithm could just be the enumerate all witnesses, and verify them, then the two definitions are equivalent, except for the verification-based one being much more intuitive.
      - etatoby 9y ago
        > [NP means that] a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time Which is exactly what quantum computers can do for certain classes of problems, such as integer factorization. Sadly, it seems not to be the case (or not yet found?) for the most well known and useful class of NP problems, NP-complete. See this discussion https://news.ycombinator.com/item?id=1371150 https://news.ycombinator.com/item?id=1371150
  - betterunix2 9y ago
    Close but no cigar. It means that you can verify a solution in polynomial time. Remember that P is contained in NP i.e. some NP problems can also be solved in deterministic polynomial time. It is widely believed that some problems in NP are not also in P, i.e. that the solutions cannot be found in polynomial time. Note that brute force may not be the most efficient way to solve such problems. For example, integer factorization is believed to not be in P, but the best known solution is much better than brute force. NP Hard problems are problems that can be used to solve all other NP problems with only polynomial time overhead. For instance, you can "encode" any NP problem as a 3COLOR problem, and then solve the 3COLOR problem instead. The reason NP hardness is interesting is that if you could solve an NP hard problem in polynomial time, then all of NP can be solved in polynomial time, so P=NP. Not all NP hard problems are actually in NP. In other words, there are some problems that can be used to solve any NP problem, but whose solutions cannot be verified in deterministic polynomial time. The problems in NP that are also NP hard are called NP complete problems; 3COLOR is an example of such a problem. If you can prove that a given NP complete problem cannot be solved in deterministic polynomial time, it means P!=NP.
    - dclowd9901 9y ago
      Thanks; better get to closing this knowledge gap
  - TheDong 9y ago
    I wouldn't count that as close for numerous reasons. If this were an interview question, I would expect discussion of NP-complete vs NP-hard at the very least. > it's impossible to predict the best solution without brute forcing all possible combinations of action That's not true; all possible combinations are not required to be checked; frequently a greedy algorithm can eliminate the majority of possibilities without actually checking them. "Impossible" is also a very strong word. Furthermore, there are plenty of problems where we currently can't solve them without bruteforce ("impossible" to do so), but we don't know if they're NP-complete/even in the NP-class. However, the really important detail you're missing which makes your answer completely wrong is the verification of the proof. If a problem is of NP Complexity, than it must be computationally easy to determine that an answer is correct in polynomial time. Your answer simply stated that a solution could be found by brute-forcing, not that the answer is easy to verify once found, and not that said brute-forcing must not be in non-polynomial time. By missing those two details, your answer is so far off the mark I'd recommend passing in an interview based on that alone.
    - brilee 9y ago
      This is one of the most distasteful "well actually" comments I've read in a while.
    - nitrogen 9y ago
      ...your answer is so far off the mark I'd recommend passing in an interview based on that alone. What kind of work do you do that requires regular detailed analysis of the complexity class of algorithms? It's been my experience that it's enough for an engineer to be able to say, "This algorithm will (not) run in an acceptable time for our expected input sizes," and that the precise definitions of NP complete and NP hard are best forgotten and looked up on Wikipedia when needed.
  - cynicaldevil 9y ago
    Not exactly, there exist various approximations for some problems which give a better solution than brute force.
  - sgrove 9y ago
    There's a fantastic video I refer to every now and then if I'm a bit unsure about it, definitely recommend it - https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s
icen 9y ago
A problem is in NP if a Turing machine, given the problem, can verify a given solution (assuming that the size of the solution is polynomial in the size of the problem) in a number of steps polynomial in the size of the problem. An example would be 3-SAT, which takes a boolean predicate of a particular form (that it is conjunctions of disjunctions of 3 variables), and then an assignment of the variables, and checks if it satisfies the predicate. You can do this in polynomial time, so 3-SAT is in NP.

What does NP stand for?

sythe2o0 9y ago

Nondeterministic Polynomial (time)

deleted 9y ago

[deleted]

cpburns2009 9y ago

"NP" stands for "nondeterministic polynomial time". See: https://en.wikipedia.org/wiki/NP_%28complexity%29 https://en.wikipedia.org/wiki/NP_%28complexity%29 (Not that I have the requisite knowledge to understand it).

dclowd9901 9y ago
I'll treat this like an interview question, and anyone can correct me if I'm wrong: My understanding of it is that it means it's impossible to predict the best solution without brute forcing all possible combinations of action... am I close there?
- icen 9y ago
  In the worst case, it is commonly thought (this is P vs NP) that you will have to test a super-polynomial number of solutions. It doesn't have to be all of them.
  - betterunix2 9y ago
    Technically you could solve the problem testing a polynomial number of solutions after spending super-polynomial time choosing the solutions to test.
- nothrabannosir 9y ago
  In addition to sibling correction, np means that a given answer can be verified in polynomial time (PTIME is an algorithm in O(n^k) for input size n and a certain constant k, as opposed to e.g. O(k^n)). An example would be travelling salesman (“is there a Hamiltonian path shorter than L for given graph?”) which you can easily verify given a path: does it visit every vertex, and is it shorter than L? Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. The finding part is P [edit: which is contained in NP]. P=NP would mean that if we can easily verify a solution , then we can also find it easily in the first place. P!=NP means that there are some problems which are easy to verify the solution for,but hard to find a solution for.
  - kevinwang 9y ago
    > Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness. Because nitpicking is fun, I'll add my contribution and say that the traditional definition of NP is actually about the finding of solutions, and is the etymology of the phrase "non deterministic polynomial time". That is, a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time. Of course, since our non deterministic algorithm could just be the enumerate all witnesses, and verify them, then the two definitions are equivalent, except for the verification-based one being much more intuitive.
    - etatoby 9y ago
      > [NP means that] a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time Which is exactly what quantum computers can do for certain classes of problems, such as integer factorization. Sadly, it seems not to be the case (or not yet found?) for the most well known and useful class of NP problems, NP-complete. See this discussion https://news.ycombinator.com/item?id=1371150 https://news.ycombinator.com/item?id=1371150
- betterunix2 9y ago
  Close but no cigar. It means that you can verify a solution in polynomial time. Remember that P is contained in NP i.e. some NP problems can also be solved in deterministic polynomial time. It is widely believed that some problems in NP are not also in P, i.e. that the solutions cannot be found in polynomial time. Note that brute force may not be the most efficient way to solve such problems. For example, integer factorization is believed to not be in P, but the best known solution is much better than brute force. NP Hard problems are problems that can be used to solve all other NP problems with only polynomial time overhead. For instance, you can "encode" any NP problem as a 3COLOR problem, and then solve the 3COLOR problem instead. The reason NP hardness is interesting is that if you could solve an NP hard problem in polynomial time, then all of NP can be solved in polynomial time, so P=NP. Not all NP hard problems are actually in NP. In other words, there are some problems that can be used to solve any NP problem, but whose solutions cannot be verified in deterministic polynomial time. The problems in NP that are also NP hard are called NP complete problems; 3COLOR is an example of such a problem. If you can prove that a given NP complete problem cannot be solved in deterministic polynomial time, it means P!=NP.
  - dclowd9901 9y ago
    Thanks; better get to closing this knowledge gap
- TheDong 9y ago
  I wouldn't count that as close for numerous reasons. If this were an interview question, I would expect discussion of NP-complete vs NP-hard at the very least. > it's impossible to predict the best solution without brute forcing all possible combinations of action That's not true; all possible combinations are not required to be checked; frequently a greedy algorithm can eliminate the majority of possibilities without actually checking them. "Impossible" is also a very strong word. Furthermore, there are plenty of problems where we currently can't solve them without bruteforce ("impossible" to do so), but we don't know if they're NP-complete/even in the NP-class. However, the really important detail you're missing which makes your answer completely wrong is the verification of the proof. If a problem is of NP Complexity, than it must be computationally easy to determine that an answer is correct in polynomial time. Your answer simply stated that a solution could be found by brute-forcing, not that the answer is easy to verify once found, and not that said brute-forcing must not be in non-polynomial time. By missing those two details, your answer is so far off the mark I'd recommend passing in an interview based on that alone.
  - brilee 9y ago
    This is one of the most distasteful "well actually" comments I've read in a while.
  - nitrogen 9y ago
    ...your answer is so far off the mark I'd recommend passing in an interview based on that alone. What kind of work do you do that requires regular detailed analysis of the complexity class of algorithms? It's been my experience that it's enough for an engineer to be able to say, "This algorithm will (not) run in an acceptable time for our expected input sizes," and that the precise definitions of NP complete and NP hard are best forgotten and looked up on Wikipedia when needed.
- cynicaldevil 9y ago
  Not exactly, there exist various approximations for some problems which give a better solution than brute force.
- sgrove 9y ago
  There's a fantastic video I refer to every now and then if I'm a bit unsure about it, definitely recommend it - https://www.youtube.com/watch?v=YX40hbAHx3s https://www.youtube.com/watch?v=YX40hbAHx3s

icen 9y ago

A problem is in NP if a Turing machine, given the problem, can verify a given solution (assuming that the size of the solution is polynomial in the size of the problem) in a number of steps polynomial in the size of the problem. An example would be 3-SAT, which takes a boolean predicate of a particular form (that it is conjunctions of disjunctions of 3 variables), and then an assignment of the variables, and checks if it satisfies the predicate. You can do this in polynomial time, so 3-SAT is in NP.