I've got this question from a course:
Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.
And it seems like this has been poorly explained and I am getting conflicting answers on how to answer. For explanation purposes I will consider my problem to be
f(x) where given a truthy value for
f(x) will output
1 and the opposite for falsey values.
In plain English, a certificate is a variable
x such that the verifier for a problem can output
In the case of
f, a certificate would be
x=0 or similar.
Is this correct?
The problems are made of a few parts:
- The problem, given x can we do y.
- A certificate, an x.
- A verifier, given y is it an actual answer for x.