4
$\begingroup$

I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem.

But we can also have NP-hard search problems. For example, it is claimed in the introduction of this paper, that finding a $k$-coloring of a $k$-colorable graph is NP-hard for $k \geq 3$. Let me call 3-COL-SEARCH the problem in which we are given a 3-colorable graph $G$, and have to output a valid 3-coloring for $G$.

For concreteness, suppose $X(G)$ is asking for the minimum number of operations to achieve something fancy for a graph $G=(V,E)$. We wish to show computing $X(G)$ is NP-hard. Technically, I should be able to do this by a reduction from 3-COL-SEARCH.

But what would we show in the reduction now? If this was a decision problem (3-COL) we are reducing from, perhaps we'd be showing "the graph $G$ is 3-colorable if and only if $X(H) \leq |V|$, where $H$ is some new graph we construct". But now I'm confused: would we show "we can find a 3-coloring for the 3-colorable graph $G$ if and only if $X(H) \leq |V|$"?

Is there perhaps some paper or resource that gives an example of such a reduction as well? I'd guess this is not so exotic.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Basically, you pick any convenient decision problem known to be NP-complete and reduce from that problem to 3-COL-SEARCH. In other words, informally, you prove that if it was possible to solve 3-COL-SEARCH in polytime, then it'd also be possible to solve that other problem in polytime.

For your particular example, a very convenient choice of decision problem is 3-COLORABLE. It's known that 3-COLORABLE is NP-complete. Now you just need to reduce 3-COLORABLE to 3-COL-SEARCH. The reduction will be super-easy: take the hypothetical algorithm for 3-COL-SEARCH, run it on the graph, check whether it has output a valid 3-coloring or not, and if yes, output "Yes", otherwise output "No". This will be a valid solution to the decision problem 3-COLORABLE, if the hypothetical algorithm correctly solves 3-COL-SEARCH.

Usually you can do the same thing with other NP-hard problems: often there is a natural decision problem associated with it, so you prove that the decision problem is NP-complete and then find a reduction from the decision problem to your search problem.

The other thing that's going on in your example is that, the way you defined 3-COL-SEARCH, it's a promise problem. A promise problem is one where we have a promise that the input will be within some set -- and the algorithm is allowed to do anything it likes on other inputs. Promise problems can be a bit counter-intuitive, or at least harder to think about, from a complexity-theory perspective, so if you're able to frame your problem so it's not a promise problem, I think that will usually be cleaner.

Improve this answer
$\endgroup$
10
  • $\begingroup$ @Gideon, Do you understand how to use a decision problem in NP to show NP-hardness? If so, use the decision problem. Usually, there's no need to use 3-COL-SEARCH (the non-NP problem) to show NP-hardness of a new problem. Instead, you can just as well use 3-COLORABLE (the decision problem, i.e., the problem in NP). I think this will make it a little easier to keep things straight. Does that solve your issue? $\endgroup$
    – D.W. ♦
    Commented Jul 27, 2015 at 17:20
  • $\begingroup$ @Gideon, ahh, the real problem is not that 3-COL-SEARCH is a search problem -- the real problem is that you're working with promise problems (where not all inputs are "allowed", e.g., there's a "promise" that the input will be 3-colorable). Do some searching on "promise problems" and I think you'll find some resources. But be warned: promise problems are weird, and they'll mess up intuition. It's usually better to reframe your problem and requirements so you don't have to think about promise problems, if you possibly can. You can have search problems that aren't promise problems. $\endgroup$
    – D.W. ♦
    Commented Jul 27, 2015 at 17:28
  • $\begingroup$ With all due respect, this answer seems unsatisfactory to me. You pinpointed the fact that we are indeed focused on a promise problem, can you then indicate the proper reduction to show hardness? Basically, I expect e.g. for 3-SAT that you have two polytime functions f and g such that phi is in 3-SAT iff g(3-COL-SEARCH(f(phi))) is 1, and f maps only to 3-colorable graphs. $\endgroup$
    – Michaël
    Commented Oct 28, 2015 at 20:52
  • 1
    $\begingroup$ @Michaël, some similar can be obtained by composing my answer with the standard reduction from 3SAT to 3COLORABLE. Let $f$ be the function associated with that reduction: it maps a satisfiable 3SAT formula $\phi$ to a 3-colorable graph $f(\phi)$, and an unsatisfiable 3SAT formula $\phi$ to a non-3-colorable graph. Let $g(G,c)$ be a function that outputs 1 if $c$ is a valid 3-coloring of $G$, or 0 otherwise. Now we have $f,g$ such that $\phi$ is in 3SAT iff $g(\text{3COLSEARCH}(f(\phi)),f(\phi))=1$. $\endgroup$
    – D.W. ♦
    Commented Oct 29, 2015 at 20:42
  • $\begingroup$ You shouldn't expect a Karp reduction from 3SAT to 3COLSEARCH, as 3COLSEARCH is a promise problem and 3SAT is not. Promise problems are weird, and you need a different notion of reduction for them. (However, I think my answer/comment does show a Turing reduction -- though I'm not an expert on promise problems, so I wouldn't swear to this being correct.) $\endgroup$
    – D.W. ♦
    Commented Oct 29, 2015 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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