Search versus Decision

Shockingly I've never done a post on search versus decision, one of the more interesting dualities in complexity. In short: Decision: Is there a needle in the haystack? Search: Find the needle.

In Satisfiability, or any other NP-complete problem, the two problems are essentially equivalent. If you can decided SAT you can find a solution (good homework problem) or even the best solution. Often people mix up the two, where people say finding the shortest Traveling Salesman Tour is NP-complete, usually without getting into too much trouble.

Decision is always at least as easy as search: If you have a solution you know there is one. What about the other direction? We can't actually prove search is hard without separating P and NP, but we have our conjectures.

Sometimes both are easy. We can easily find the maximum weighted matching.

Sometimes decision is easy and search is supposedly hard: Composite Numbers. The search version is factoring.

Sometimes decision is trivial (i.e. they always exist) and search is still hard. Nash Equilibria. Ramsey Graphs.

Often we ask whether search reduces to decision? If you have some oracle (magic black box) that answered search questions, can you solve the decision problem efficiently? SAT has this property, as does Matching (for trivial reasons). Nash Equilibrium and Composite Numbers likely don't.

Graph Isomorphism does, i.e., given an oracle for graph isomorphism you can find the isomorphism (another good homework problem).

There's also an interesting non-adaptive version. Given a SAT formula can you find an assignment with questions to a SAT oracle that all have to be asked at the same time?

Here we get a probable yes. If the formula has one solution you can find it by asking for each bit of the solution. Randomly you can reduce SAT to several formulas, one of which is likely to have a single assignment that is also an assignment of the original formula. With standard hardness assumptions you can eliminate the randomness.

Is the same true for graph isomorphism? I think that's still open.
Computational Complexity published first on Computational Complexity