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 ]
Randy

Posts: 19
Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 4:10 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

stephen@nomail.com wrote:
> In comp.theory Randy <joe@burgershack.com> wrote:
>
>

>>To wit, the solution of 3-SAT or any X^N problem requires exponential
>>runtime (right?).

>
>
> No, we do not know that 3-SAT requires exponential runtime.
> Nobody has ever found a non-exponential algorithm for 3-SAT,
> but that does not mean one does not exist.


So the identification of a problem as being NP-Hard is its *absence* of
a polynomial solution? If the problem is not as easy as X, then we say
only that it's not as easy as other un-easy problems?

No wonder I'm confused. I've always had trouble with double negatives.

>
> What do you mean by an X^N problem? Do you have an example
> in mind?


AKA exponential. No doubt I've messed up that term too...

Randy

>
> Stephen


--
Randy Crawford http://www.ruf.rice.edu/~rand rand AT rice DOT edu


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.