1
$\begingroup$

When we learn about P versus NP, we are taught that a certificate for a problem in NP can be verified (or invalidated) in polynomial time. But then the proof that $P \subseteq NP$ ignores the requirement to verify the given certificate, and says that we can just use our deterministic polynomial-time solver algorithm to determine if the true answer is "Yes" or "No." In doing so, we will have solved the problem, but we have not necessarily verified the certificate that was presented.

For example, Djikstra's algorithm solves the shortest path problem in polynomial time, but as a constructive algorithm, it is not equipped to verify a solution. Suppose we have a shortest path decision problem instance where the true answer is "Yes," and suppose I give you an invalid certificate containing an incomplete path. Finally, suppose my path length is less than the threshold, so I falsely claim to have a "Yes" certificate. If you invoke Djikstra's algorithm, it will show that the decision problem's answer is "Yes," but it doesn't show that my certificate is invalid. So by invoking Djisktra's algorithm, you end up "verifying" my invalid claim.

Have I missed some nuance to these definitions that establishes an equivalence between "verify the certificate" and "solve the problem"?

$\endgroup$

1 Answer 1

2
$\begingroup$

Verifying a solution is a separate process from solving the problem. The proof that $P \subseteq NP$ relies on the fact that a problem in $P$ is by definition of $P$ assumed to have the ability to verify a "yes" problem (e.g., confirm that the optimal objective value is at most whatever) in polynomial time (satisfying that requirement for $NP$).

For the shortest path problem, checking a solution is simple (and has nothing to do with Dijkstra's algorithm): check that the first arc starts where it should (constant time); check that the last arc ends where it should (constant time); check that each arc connects to the preceding/following arc (time proportional to the number of arcs in the path, which is bounded by the number of arcs in the graph); and add up the arc lengths (time again proportional to the number of arcs) and verify it meets the threshold.

$\endgroup$
4
  • $\begingroup$ Thank you for this response. I agree that your verifier algorithm works, but this further demonstrates my point that you cannot simply call the solver algorithm (i.e., Djisktra) to "double-hat" as your verifier. You state that having a polynomial verifier is a requirement for being in P (in addition to the usual requirement for a polynomial solver algorithm). Can you provide a reference for this? $\endgroup$
    – Tim
    Commented May 16, 2022 at 15:36
  • $\begingroup$ We need to be very cautious here, because complexity theory is nitpicky beyond what even tax lawyers can tolerate. The definition of class P does not require that any certificate of a "yes" problem be verifiable in polynomial time; it just requires that every "yes" problem have a certificate verifiable in polynomial time. For a problem in class P, you produce such a certificate by solving the problem (in polynomial time). The algorithm (for instance, Dijkstra), does not have to verify other hypothetical certificates (solutions); it just needs to produce on in poly-time. $\endgroup$
    – prubin
    Commented May 16, 2022 at 19:27
  • $\begingroup$ You can find something along these lines in "Combinatorial Optimization" by Papadimitriou and Steiglitz. (Disclaimer: I am by no means an expert on complexity theory, since I usually run screaming in the opposite direction as soon as it is mentioned.) $\endgroup$
    – prubin
    Commented May 16, 2022 at 19:29
  • $\begingroup$ I just edited my answer -- I got a bit loose with things in the first paragraph. $\endgroup$
    – prubin
    Commented May 16, 2022 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.