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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Joe Hendrix Posts: 4 Registered: 10/11/05
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 2:35 PM
 Plain Text Reply

Randy wrote:
> Perhaps that's because it doesn't serve them to make the argument. Why
> pick fights that aren't worth the trouble? (I'm certainly sympathetic
> to this argument at the moment...)

Perhaps it is also because they are smart enough to realize its
importance. Complexity theory is a big field, and one could get a lot
of fame as a researcher by finding a solid line of reasoning that it is
irrelevant. I personally think that there is too much of a focus on
worst-case running time at the undergraduate level, but admitadly other
types of analysis are usually even harder to do correctly.

> Maybe that was because it's just too much trouble
> to ask others to prove their algorithms to be NPC (or NP-Hard)

This suggests you still don't understand what NP complete and NP hard
mean. Algorithms are not NP complete, problems are. Algorithms may
have a polynomial time running time, an exponential time, or something
even worse. A good algorithm doesn't even have to always terminate to
be useful -- Knuth-Bendix completion is a good example of an important
algorithm that does not.

> I'd be interested to know some examples of CS non theorists (e.g.
> informal algorithmists) who have found formal NP (as opposed to simple
> algorithmic complexity) valuable other than to imply exponentiality or
> infeasibility.

Well, I am not in theory and find NP completeness useful. I don't know
what you mean by informal algorithmists though. A computer science
algorithm is by definition a formal entity. How do you expect a machine
to execute an informal algorithm? In my experience in automated reasoning,
NP completeness is a good result to achieve, since it suggests that
techniques like SAT solving or linear arithmetic decision procedures may
be able to efficiently solve problems in practice. Higher complexity
classes usually require more exhaustive search.

This discussion might make since if you were talking about some exotic
class perhaps involving machines with oracles, but NP completeness is a
very basic concept.

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

© The Math Forum at NCTM 1994-2018. All Rights Reserved.