Methods of turning a decision problem into finding the certificate?

Question

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it's yes, how can we go from that to finding a polynomial-time algorithm that gives the certificate?

For example, let's say I have a CNF formula. Let's assume we have an algorithm that outputs whether a formula is satisfiable, in polynomial time. I want to know what the actual assignment is. So I'd do a for loop (for i from 1 to n, where n is the number of variables). At each step, I can do one more assignment (assign the i'th variable to be true) and check if the new formula with the i'th value set, is still satisfiable. If yes, continue. Otherwise, assign the i'th variable to be false, and then continue. By saving each of these assignments, at the end I can output a list.

My question is, are there some good methods (in general) of finding the certificate? Perhaps some "token problems" where if you know what to do with one problem of that type, you can do all problems of that type (eg, graph theory, network design, sets/partitions, algebra/number theory, satisfiability)?

Answer 1

The main method is self-reducibility. Suppose that your problem is of the form "there exists an object $x$ such that $P(x)$". Consider some partition of the set of all possible objects $O$, say $O = O_1 \cup \cdots \cup O_m$ (here $m$ should be "small", i.e. polynomial in the size of $x$). If the problem "there exists an object $x \in O_i$ such that $P(x)$" can be reduced to your original problem, then you can use a recursive approach for finding some certificate. The reduction should have the property that a witness for the reduced problem implies a witness for the original problem.

SAT, the example in the question, has exactly this property. In this case, $x$ is a truth assignment, and $P(x)$ states that $x$ satisfies some formula. For each variable $x_i$ we can partition the set $O$ of all truth assignments into $O = O_{i,true} \cup O_{i,false}$ according to the value of $x_i$. The problem "there exists a truth assignment $x \in O_{i,val}$ such that $P(x)$" (where $val$ is either $true$ or $false$) is also a SAT problem. We can use this to figure out a truth assignment satisfying $P$.

A more interesting example is 3-colorability. In this case $x$ is a 3-coloring and $P(x)$ states that $x$ is a valid coloring for the input graph. For any two unconnected vertices $v,w$, we can consider the partition $O = O_{v=w} \cup O_{v\neq w}$, according to whether $x(v) = x(w)$ or not. We can reduce the problem "there exists $x \in O_{v=w}$ such that $P(x)$" into an instance of 3-coloring by merging $v$ and $w$. We can reduce the problem "there exists $x \in O_{v\neq w}$ such that $P(x)$" into an instance of 3-coloring by adding the edge $(v,w)$.