3
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Cool, thanks for clearing that up. So otherwise, my argument is correct, including the equivalency part? Sorry for sounding incredulous, I was just really convinced I went wrong there. $\endgroup$ – cadaniluk Jul 15 '18 at 17:14
  • $\begingroup$ Unfortunately I don't really understand the rest of your argument. $\endgroup$ – Yuval Filmus Jul 15 '18 at 17:15
  • $\begingroup$ Then let me rephrase a little: my algorithms book proves that the circuit satisfiability problem is NP-complete. To prove that every problem in $NP$ is reducible to circuit-SAT, a characteristic of NP-completeness, it restates what a reduction algorithm tries to achieve at all. It reads "Given an input $x$, it must compute a circuit $C = f(x)$ that is satisfiable if and only if there exists a certificate $y$ such that $A(x, y) = 1$. $f$ is the reduction function computed by the reduction algorithm here. $\endgroup$ – cadaniluk Jul 15 '18 at 17:30
  • 1
    $\begingroup$ Yes, it's the same thing. $\endgroup$ – Yuval Filmus Jul 15 '18 at 17:32
  • 2
    $\begingroup$ It's not feasible. This is why NP-hard problems are hard. $\endgroup$ – Yuval Filmus Jul 15 '18 at 17:37

Your Answer

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

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