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)?
Methods of turning a decision problem into finding the certificate?
complexity theory;reductions;polynomial time