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 ]
 stephen@nomail.com Posts: 1,744 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 27, 2005 4:28 PM

In comp.theory Randy <joe@burgershack.com> wrote:
> 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?

No. A problem is NP-hard if every problem in NP is polynomially
reducible to it. Nobody currently knows if polynomial time solutions exist
for any NP-Hard problems. If you were to find a polynomial solution
for an NP-Hard problem then you have proven that P=NP. If you
prove that no polynomial time algorithm exists for an NP-Complete
problem then you have proven that P<>NP. If you prove that
no polynomial time algorithm exists for an NP-Hard problem, it
may still be the case that P=NP because not all NP-Hard problems
are in NP.

> If the problem is not as easy as X, then we say
> only that it's not as easy as other un-easy problems?

Currently all we can say for the most part is how hard certain problems
are relative to each other. We know of a whole bunch of problems
that are all just as hard as each other in the sense that
if a polynomial time solution existed for any of them one would
exist for all of them. However we do not know if those polynomial
solutions exist or not. It seems doubtful that they do, but
who knows what some clever person down the road may think of.

> 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...

But what problem do you have in mind? Remember there is
a difference between a problem and an algorithm. We do not
know that 3-SAT is an exponential problem. There are very
few problems that we know for a fact require exponential time.
We do know that 3-SAT is NP-complete, and lots of people suspect
that means that there does not exist a polynomial time algorithm
for 3-SAT, but we do not actually know that.

Stephen

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