5 ms·

It is nitpicky, but the fact that these classes deal with decision problems and not general problems is something which feels like should be mentioned more ofte

It is nitpicky, but the fact that these classes deal with decision problems and not general problems is something which feels like should be mentioned more often. 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.

tromp 4y ago
Your conversion doesn't address determining the length of the output. Another conversion avoids that issue, by converting a polynomial time function f into the language L_f = { (x,y): f(x) < y}, where < compares strings lexicographically "" < "0" < "1" < "00" ... Given a decider for L_f and an input x it's easy to determine |f(x)| and next f(x) by binary search.
NotOscarWilde 4y 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.
- tromp 4y 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.
  - NotOscarWilde 4y 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.
    - tromp 4y 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.

tromp 4y ago

Your conversion doesn't address determining the length of the output. Another conversion avoids that issue, by converting a polynomial time function f into the language L_f = { (x,y): f(x) < y}, where < compares strings lexicographically "" < "0" < "1" < "00" ... Given a decider for L_f and an input x it's easy to determine |f(x)| and next f(x) by binary search.

NotOscarWilde 4y 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.

tromp 4y 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.
- NotOscarWilde 4y 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.
  - tromp 4y 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.