4 ms·

> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for, but extremely difficult for computers to solve. [...]

by _greim_ 13y ago

> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for, but extremely difficult for computers to solve. [...] All P problems are NP problems Seems like a direct contradiction. Typo, or am I missing something?

tanderson11 13y ago
All P problems are in NP. If you can solve a problem in polynomial time, you could simply "check" the problem on an input by solving the problem and seeing if the test input were in the set of solutions. It will clearly take P time to perform that "check" (because you can solve the problem in P time). This means all problem in P must be in NP. The error is that not all problems in NP are "extremely difficult for computers to solve". The difficulty of solving problems in NP varies drastically between particular problems.
14113 13y ago
Sort of - we don't know if NP problems are hard for computers to solve, that's really the whole question! Technically, P is a subset of NP. Problems in NP have answers (called certificates) which can be verified, or checked, using an algorithm that runs in polynomial time (that is asymptotically O(n^x), where X is a finite integer). Problems that are in P are those that have a polynomial time algorithm to construct an answer. Any problem that's in P is therefore in NP, as we can simply run the algorithm for constructing the answer then compare it with the certificate to see if they match. P vs NP simply asks if all problems in NP can be solved in polynomial time, hence P=NP.
- _greim_ 13y ago
  Ahh. Thank you. This actually makes more sense than the article itself!
sherjilozair 13y ago
If you can solve something easily, then you can also verify its solutions easily. It is a typo. It should say "but potentially extremely difficult for computers to solve."
peeters 13y ago
This is coming from my suggestion above, but in my suggestion, I omitted "but extremely difficult for computers to solve", leaving it with: > P problems are easy for computers to solve, and NP problems are easy for computers to check answers for. The problem is the text still uses "NP problems" and "NP complete problems" interchangeably, when it shouldn't. (The diagram at the top gets it right!)

by _greim_ 13y ago

tanderson11 13y ago

All P problems are in NP. If you can solve a problem in polynomial time, you could simply "check" the problem on an input by solving the problem and seeing if the test input were in the set of solutions. It will clearly take P time to perform that "check" (because you can solve the problem in P time). This means all problem in P must be in NP. The error is that not all problems in NP are "extremely difficult for computers to solve". The difficulty of solving problems in NP varies drastically between particular problems.

14113 13y ago

Sort of - we don't know if NP problems are hard for computers to solve, that's really the whole question! Technically, P is a subset of NP. Problems in NP have answers (called certificates) which can be verified, or checked, using an algorithm that runs in polynomial time (that is asymptotically O(n^x), where X is a finite integer). Problems that are in P are those that have a polynomial time algorithm to construct an answer. Any problem that's in P is therefore in NP, as we can simply run the algorithm for constructing the answer then compare it with the certificate to see if they match. P vs NP simply asks if all problems in NP can be solved in polynomial time, hence P=NP.

_greim_ 13y ago
Ahh. Thank you. This actually makes more sense than the article itself!

sherjilozair 13y ago

If you can solve something easily, then you can also verify its solutions easily. It is a typo. It should say "but potentially extremely difficult for computers to solve."

peeters 13y ago

This is coming from my suggestion above, but in my suggestion, I omitted "but extremely difficult for computers to solve", leaving it with: > P problems are easy for computers to solve, and NP problems are easy for computers to check answers for. The problem is the text still uses "NP problems" and "NP complete problems" interchangeably, when it shouldn't. (The diagram at the top gets it right!)