1
$\begingroup$

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 x 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 1 or 0. In the case of f, a certificate would be x=1 or 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.
Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

For example, the compositeness problem, "given an integer $X$, is it composite?" might have a certificate $n_1, n_2$ where $X=n_1n_2$. This certificate would be checkable in time polynomial in the length of the certificate.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The certificate is the possible solution n1, n2 for X. The verifier in this case is simply n1 * n2 == N, which is obviously p time. When we say we want to "find a certificate" that means we want to construct those n's but not actually bother solving it. Just the format for a certificate? $\endgroup$
    – Derek C.
    Commented Dec 7, 2020 at 17:56
  • $\begingroup$ Correct. All you have to do is provide a polynomial-time algorithm which, when implemented, shows that a particular instance does or does not satisfy the decision problem. $\endgroup$
    – Rick Decker
    Commented Dec 9, 2020 at 0:43
  • $\begingroup$ Ok so forgive me but this seems absolutely pointless. It's just "choose some random numbers". I don't see how constructing a certificate is ever a hard problem. $\endgroup$
    – Derek C.
    Commented Dec 9, 2020 at 5:57
  • 1
    $\begingroup$ The point is that a certificate says, essentially, "Here's how we could quickly establish whether we have a solution or not." The point being that for some problems, finding a solution seens to be considerably more time-comsuming than verifying a solution. $\endgroup$
    – Rick Decker
    Commented Dec 9, 2020 at 15:45
  • 1
    $\begingroup$ You have misread the question. It states: "Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.". I presume what the book's author is asking for is how given an oracle for a decision problem, we can find the solution to the corresponding search/optimization problem. The use of the word "certificate" is confusing (though it probably makes sense in the context of the book). $\endgroup$
    – Tom van der Zanden
    Commented Jan 6, 2021 at 18:16
1
$\begingroup$

You need an algorithm so that if you have a problem p(x), and a certificate c(x), then your algorithm can either tell correctly what the answer to p(x) is, or determine that the certificate is not valid.

For example, if the problem p(x) is "find a non-trivial factor of x", which may be hard to do, then any factor of x is a valid certificate (you just try dividing x by the factor, and if there is no remainder then you have a non-trivial factor of x, and if there is a remainder then you know you have an invalid certificate).

Your example c(x)=1 or c(x)=0 is not a certificate. If I give you one of these, then you still have to solve the problem yourself, because otherwise you don't know whether the certificate was valid or invalid.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You have misread the question. It states: "Show how to efficiently find a certificate for each of the following problems assuming that the decision problem is efficiently solvable.". I presume what the book's author is asking for is how given an oracle for a decision problem, we can find the solution to the corresponding search/optimization problem. The use of the word "certificate" is confusing (though it probably makes sense in the context of the book). $\endgroup$
    – Tom van der Zanden
    Commented Jan 6, 2021 at 18:15

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.