
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 7:26 PM


In article <djrln4$f8l$1@joe.rice.edu>, Randy <joe@burgershack.com> wrote: >Interesting. I'd never thought of each step in a game as being a >problem in its own right. But is that a decision problem?
It's easy to cast, say, chess as a decision problem. For example: Given a position, is it a forced win for White? This is a yesno question. If I have the ability to answer this question, then I can play Black and ensure that I never lose a game in which I have a forced win or draw, as follows. Whenever it's my turn, I hypothetically try each of my possible moves (there are only polynomially many such) and ask "forced win for White?" for each of the resulting positions. Then I pick a move (if any) for which the answer comes back "no."
By the way, informal reasoning may be helpful here: obviously, when I'm playing a game, I'm faced with a constant sequence of "decisions" (what would be a winning move for me to play now?) in an informal sense, so it should not be surprising that I can formally collect all the possible situations I might be faced with, and define a decision problem accordingly.
>I *think* I remember that any optimization problem can be converted into >a decision problem.
This is true in practice (I'm not sure offhand if one can construct pathological cases where this fails). Let's say that the optimization problem is to find, for any given instance, a solution of least cost (where cost is assumed to be nonnegative). Then the associated decision problem is, "Given an instance X and a threshold T, does there exist a solution whose cost is at most T?" In most cases, if you can answer this question, you can compute the optimum cost by a bisection algorithm. For example, you might be able to compute a poor but feasible solution easily and find that its cost is (say) 2^20. Then ask, does there exist a solution with cost <= 2^19? If yes, ask if there's a solution with cost <= 2^18, and so on.
Typically you can even construct a solution (not just find the best cost) if you can solve an associated decision problem. For example, suppose I want to color a graph with the minimum number of colors. The associated decision problem would be, "Given a partially colored graph G and a threshold T, can the partial coloring be completed to a full coloring using at most T colors?" Then you can color the graph one node at a time, trying each possible color and picking one that your infallible decision maker says is O.K. (Note that you never need to backtrack if the decision maker is indeed infallible.)  Tim Chow tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. Galileo, Dialogues Concerning Two New Sciences

