3 ms·

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 certa

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

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