3 ms·

Quite literally! http://theconversation.com/millennium-prize-p-vs-np-4246 http://theconversation.com/millennium-prize-p-vs-np-4246

tlb 8y ago
NP means that a solution can be verified to be valid. Like the reviewer saying “yep, this is a car all right”. But verifying whether a solution is optimal is not generally even in NP.
- mygo 8y ago
  You can use the decision version of an optimization problem to answer the optimization problem. For example when you're looking for the fastest route, you're not directly asking "is this the fastest route?" You're asking "Is there a route shorter than length x?" It's a yes or no question, that's easy to verify given a certificate. If the answer is "yes" then the certificate is a route produced that is shorter than length x. Assuming the existence of an algorithm that can reliably produce a verifiable "yes" with a certificate or "no", you ask "Is there a route shorter than length x?" and if the answer is yes (which you can easily verify), you keep reducing the length of x in the question until the answer to the question is not yes (no certificate can be produced). The certificate of the limiting "yes" is the optimal solution.
  - tlb 8y ago
    That technique isn't as powerful as sometimes believed. In your example, you've assumed the uncomputable thing, an algorithm which reliably produces a solution to a problem for which one exists. Consider, "Is there a proof in fewer than x lines of the Riemann hypothesis?"
    - mygo 8y ago
      I don’t think that a candidate solution to your problem statement can be deterministically verified in polynomial time. Any candidate solution produced would be subjective to the interpreter who is verifying it as to whether it satisfies the requirements of a proof (maybe they want more definitions, less shorthand notation, maybe in french, references in APA style with full names, etc, all of which would effect the length of the proof). So whereas a candidate solution to your question is difficult to verify, it is not in this P vs NP discussion.

tlb 8y ago

NP means that a solution can be verified to be valid. Like the reviewer saying “yep, this is a car all right”. But verifying whether a solution is optimal is not generally even in NP.

mygo 8y ago
You can use the decision version of an optimization problem to answer the optimization problem. For example when you're looking for the fastest route, you're not directly asking "is this the fastest route?" You're asking "Is there a route shorter than length x?" It's a yes or no question, that's easy to verify given a certificate. If the answer is "yes" then the certificate is a route produced that is shorter than length x. Assuming the existence of an algorithm that can reliably produce a verifiable "yes" with a certificate or "no", you ask "Is there a route shorter than length x?" and if the answer is yes (which you can easily verify), you keep reducing the length of x in the question until the answer to the question is not yes (no certificate can be produced). The certificate of the limiting "yes" is the optimal solution.
- tlb 8y ago
  That technique isn't as powerful as sometimes believed. In your example, you've assumed the uncomputable thing, an algorithm which reliably produces a solution to a problem for which one exists. Consider, "Is there a proof in fewer than x lines of the Riemann hypothesis?"
  - mygo 8y ago
    I don’t think that a candidate solution to your problem statement can be deterministically verified in polynomial time. Any candidate solution produced would be subjective to the interpreter who is verifying it as to whether it satisfies the requirements of a proof (maybe they want more definitions, less shorthand notation, maybe in french, references in APA style with full names, etc, all of which would effect the length of the proof). So whereas a candidate solution to your question is difficult to verify, it is not in this P vs NP discussion.