Hacker News new | ask | show | jobs
by NotOscarWilde 1217 days ago
> Of course this ends up not mattering in practice since we can convert a problem with arbitrary (bitstring) output into a decision problem.

Not always. My favorite counter-example is coloring k-colorable graphs. Consider that for some reason (and there could be many), you are guaranteed that all the graphs on input are k-colorable. Still, the input is just a graph without any coloring. Your algorithm is tasked to find a proper coloring using the smallest number of colors.

It is both a problem that has been already studied in terms of approximation and at the same time an optimization problem that has no good decision version, as far as I am aware.
1 comments
tromp 1217 days ago
> Your algorithm is tasked to find a proper coloring using the smallest number of colors.

That's not an NP type problem, in the sense that you cannot verify in polynomial time whether a coloring is minimal or not.

link
NotOscarWilde 1217 days ago
> That's not an NP type problem

The comment I was referring to was talking about "decision problems and general problems" and there always being a reduction between them.

Now "general problems" is a bit vague, but in my classes on optimization the students are intuitively led to believe that optimization problems always have a decision problem associated with them, so we can talk about NP-hardness of optimization problems, too. Which is often true, but not always.

As a good example, if you consider graph coloring, you can argue that the associated decision problem is "given a graph G, and a parameter k, answer yes if G is colorable with at most k colors". This way, slightly informally, you can talk about NP-hardness of finding the smallest number of colors for a graph.

However, the optimization problem I presented -- coloring k-colorable graphs -- is a valid optimization problem, it is interesting and has been studied in the past, but it has no good decision problem associated with it.

link
tromp 1216 days ago
> it has no good decision problem associated with it.

I disagree. You can efficiently find a k-coloring of any k-colorable graph if you can efficiently decide what graphs are k-colorable.

link