Randy
Posts:
19
Registered:
12/13/04


Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 6:52 PM


tchow@lsa.umich.edu wrote: > In article <djr27u$fa$1@joe.rice.edu>, Randy <joe@burgershack.com> wrote: > >>OK. In lay terms (as the OP requested), why is NP meaningful to >>practitioners? What utilitarian subtlety does it capture that >>"exponential" does not? > > > As you mentioned elsewhere, part of your difficulty may be that problems > that are beyond NP do not arise in practice as often. However, there is > one familiar type of problem that is not (known to be) in NP, namely the > playing of strategy games such as chess or go. Depending on exactly how > you choose to generalize these games to arbitrarily large boards, they > are at least PSPACEcomplete and sometimes EXPcomplete. You can see > intuitively that they are not (known to be) in NP, because even if I'm > a chessplaying god and can tell you what the best move in any given > position is, there's no easy way for you to verify that it's the best > move. The chessplaying god could give you a huge table of possibilities > as proof, but checking the huge table takes exponential time, rather than > polynomial time.
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? Because *any* solution to 3SAT is a success, whereas it's likely that only one move in a game of chess or one choice in continuing a path through a TSP solution will lead to an optimal solution.
It also seems like there must be some sort of linear sequential factor to be considered in solving games, since the moves that come before must dictate the value of the alternative subsequent moves.
I *think* I remember that any optimization problem can be converted into a decision problem. Perhaps I'm just not seeing how searchdriven problems (chess, TSP, A*, etc) can be so reformulated.
> > Practically speaking, knowing that there's a difference between playing > strategy games and solving NPcomplete problems means that if you have > your eye on writing a killer go program that will beat all the competition > and sell millions of copies in East Asia, then you will know better than > to, say, attempt to formulate the problem as an integer linear program > and throw CPLEX at it. Nor will you waste time studying Hochbaum's > "Approximation Algorithms for NPHard Problems" or Downey and Fellows's > "Parameterized Complexity" even though both books contain much valuable > material on algorithms for hard problems.
OK. I'm convinced. It's time to reevaluate. Thanks,
Randy
 Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu

