patternMinor
How is deciding a problem not equivalent to finding a valid certificate for verification?
Viewed 0 times
problemcertificateequivalentfindingdecidingvalidhowfornotverification
Problem
Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$.
Since $Q$ is in $NP$, there exists a verification algorithm $A$, which takes an input and a certificate, in that order, as arguments and maps those to $\lbrace 0, 1 \rbrace$, depending on whether there exists a certificate proving that the solution to the input is $1$.
If this presentation of what a verification algorithm does is correct, then it is unclear to me if, for a binary-encoded problem instance $x$,
$$Q(x) = 1 \iff \exists y (A(x, y) = 1).$$
It seems to me that if there is a certificate, this means that the decision for that input is affirmative, so that in theory, you could attach sufficient information to a certificate such that it characterizes a solution to the decision problem, iterate through the entire set of certificates and, once you have found one that satisfies $A(x, y) = 1$, you have also found a solution to the problem for the respective input.
Maybe someone could explain to me if that equivalency above is wrong and if so, why. I know the difference between a problem and the verification part, but then again, on some level I do not.
Neither am I sure about anything else, so feel free to point out mistakes.
Since $Q$ is in $NP$, there exists a verification algorithm $A$, which takes an input and a certificate, in that order, as arguments and maps those to $\lbrace 0, 1 \rbrace$, depending on whether there exists a certificate proving that the solution to the input is $1$.
If this presentation of what a verification algorithm does is correct, then it is unclear to me if, for a binary-encoded problem instance $x$,
$$Q(x) = 1 \iff \exists y (A(x, y) = 1).$$
It seems to me that if there is a certificate, this means that the decision for that input is affirmative, so that in theory, you could attach sufficient information to a certificate such that it characterizes a solution to the decision problem, iterate through the entire set of certificates and, once you have found one that satisfies $A(x, y) = 1$, you have also found a solution to the problem for the respective input.
Maybe someone could explain to me if that equivalency above is wrong and if so, why. I know the difference between a problem and the verification part, but then again, on some level I do not.
Neither am I sure about anything else, so feel free to point out mistakes.
Solution
The problem is in the following excerpt:
iterate through the entire set of certificates
There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.
Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.
iterate through the entire set of certificates
There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.
Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.
Context
StackExchange Computer Science Q#95286, answer score: 8
Revisions (0)
No revisions yet.