Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: On NP Completeness and Intractability
Replies: 90   Last Post: Nov 1, 2005 8:08 PM

 Messages: [ Previous | Next ]
 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 PSPACE-complete and sometimes EXP-complete. You can see
> intuitively that they are not (known to be) in NP, because even if I'm
> a chess-playing 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 chess-playing 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 3-SAT 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 search-driven
problems (chess, TSP, A*, etc) can be so reformulated.

>
> Practically speaking, knowing that there's a difference between playing
> strategy games and solving NP-complete 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 NP-Hard 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

Date Subject Author
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 Dr. David Kirkby
10/25/05 ianparker2@gmail.com
10/25/05 Pubkeybreaker
10/25/05 osmium
10/25/05 Pubkeybreaker
10/25/05 Willem
10/25/05 Bryan Olson
10/25/05 Willem
10/25/05 Ed Prochak
10/25/05 Dr. David Kirkby
10/25/05 Gene
10/25/05 MartDowd
10/25/05 RobertSzefler
10/25/05 Dr. David Kirkby
10/25/05 Pubkeybreaker
10/25/05 Wim Benthem
10/26/05 RobertSzefler
10/25/05 KP Bhat
10/25/05 stephen@nomail.com
10/25/05 tchow@lsa.umich.edu
10/25/05 googmeister@gmail.com
10/25/05 nimmi_srivastav@yahoo.com
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/27/05 stephen@nomail.com
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 C6L1V@shaw.ca
10/25/05 stephen@nomail.com
10/25/05 Wim Benthem
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/26/05 tchow@lsa.umich.edu
10/26/05 Randy
10/27/05 Arthur J. O'Dwyer
10/27/05 Randy
10/27/05 Willem
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 tchow@lsa.umich.edu
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 Joe Hendrix
10/27/05 Randy
10/27/05 stephen@nomail.com
10/27/05 Arthur J. O'Dwyer
10/27/05 googmeister@gmail.com
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/27/05 Arthur J. O'Dwyer
10/28/05 Joe Hendrix
10/28/05 Ben Rudiak-Gould
10/28/05 Bryan Olson
10/28/05 Pekka Orponen
10/27/05 tchow@lsa.umich.edu
10/27/05 Randy
10/25/05 tchow@lsa.umich.edu
10/25/05 Michael J. Hennebry
10/25/05 stephen@nomail.com
10/25/05 Randy
10/25/05 stephen@nomail.com
10/25/05 Willem
10/25/05 Arthur J. O'Dwyer
10/25/05 googmeister@gmail.com
10/31/05 Oliver Wong
10/31/05 Robert Israel
11/1/05 Willem
11/1/05 googmeister@gmail.com
11/1/05 Willem
11/1/05 Torkel Franzen
11/1/05 googmeister@gmail.com
11/1/05 Oliver Wong
11/1/05 Willem
11/1/05 Robert Israel
10/26/05 Randy
10/26/05 stephen@nomail.com
10/26/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/27/05 Bryan Olson
10/27/05 Randy
10/25/05 Pat Farrell
10/25/05 Bryan Olson