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.
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.