> in fact “convert NP-complete problem to SAT” is in P.
is not the most precise, since P is a class of decision problems, while said conversion [2] is not a decision problem, but something that runs in polynomial time.
Of course this ends up not mattering in practice since we can convert a problem with arbitrary (bitstring) output into a decision problem. To do this we just include a index n in the input and make the decision problem about whether the bit at given index n is 1.
L_f = { (x,y): f(x) < y},
Given a decider for L_f and an input x it's easy to determine |f(x)| and next f(x) by binary search.
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.
That's not an NP type problem, in the sense that you cannot verify in polynomial time whether a coloring is minimal or not.
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.
I disagree. You can efficiently find a k-coloring of any k-colorable graph if you can efficiently decide what graphs are k-colorable.