Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Joe Hendrix

Posts: 4
Registered: 10/11/05
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 2:35 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic 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
Read On NP Completeness and Intractability
nimmi_srivastav@yahoo.com
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
ianparker2@gmail.com
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
osmium
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Ed Prochak
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
Gene
10/25/05
Read Re: On NP Completeness and Intractability
MartDowd
10/25/05
Read Re: On NP Completeness and Intractability
RobertSzefler
10/25/05
Read Re: On NP Completeness and Intractability
Dr. David Kirkby
10/25/05
Read Re: On NP Completeness and Intractability
Pubkeybreaker
10/25/05
Read Re: On NP Completeness and Intractability
Wim Benthem
10/26/05
Read Re: On NP Completeness and Intractability
RobertSzefler
10/25/05
Read Re: On NP Completeness and Intractability
KP Bhat
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/25/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/25/05
Read Re: On NP Completeness and Intractability
nimmi_srivastav@yahoo.com
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
C6L1V@shaw.ca
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Wim Benthem
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Willem
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/27/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/28/05
Read Re: On NP Completeness and Intractability
Joe Hendrix
10/28/05
Read Re: On NP Completeness and Intractability
Ben Rudiak-Gould
10/28/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/28/05
Read Re: On NP Completeness and Intractability
Pekka Orponen
10/27/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
tchow@lsa.umich.edu
10/25/05
Read Re: On NP Completeness and Intractability
Michael J. Hennebry
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/25/05
Read Re: On NP Completeness and Intractability
Willem
10/25/05
Read Re: On NP Completeness and Intractability
Arthur J. O'Dwyer
10/25/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
10/31/05
Read Re: On NP Completeness and Intractability
Oliver Wong
10/31/05
Read Re: On NP Completeness and Intractability
Robert Israel
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
Torkel Franzen
11/1/05
Read Re: On NP Completeness and Intractability
googmeister@gmail.com
11/1/05
Read Re: On NP Completeness and Intractability
Oliver Wong
11/1/05
Read Re: On NP Completeness and Intractability
Willem
11/1/05
Read Re: On NP Completeness and Intractability
Robert Israel
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/26/05
Read Re: On NP Completeness and Intractability
stephen@nomail.com
10/26/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/27/05
Read Re: On NP Completeness and Intractability
Bryan Olson
10/27/05
Read Re: On NP Completeness and Intractability
Randy
10/25/05
Read Re: On NP Completeness and Intractability
Pat Farrell
10/25/05
Read On what "NP-Hard" means; was: Re: On NP Completeness and Intractability
Bryan Olson

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.