2
$\begingroup$

Can I build a polynomial time verifier for problem, given a non-deterministic polynomial time decider for that problem?

I assume I should modify the decider such that it will verify the certificate. Can I use the given decider as is (without any modification)?

$\endgroup$
  • 1
    $\begingroup$ Yes, if the problem is in P then any (empty) certificate will do, as you can check the solution in polynomial time by reconstructing it. $\endgroup$ – Albert Hendriks Jul 11 '17 at 3:52
  • 1
    $\begingroup$ @AlbertHendriks Make a full-fledged answer? $\endgroup$ – Yuval Filmus Jul 11 '17 at 6:42
  • $\begingroup$ @AlbertHendriks The problem is not necessarily in P. $\endgroup$ – Joey Kaller Jul 11 '17 at 9:51
  • $\begingroup$ I see. I think it depends on the context. Any P verifier automatically leads to an NP decider and vice versa, but there are syntactic/semantic differences. The input to the verifier is the same as the certificate for the decider, but "certificate" is not equivalent to "input" $\endgroup$ – Albert Hendriks Jul 11 '17 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.