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

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 ]
C6L1V@shaw.ca

Posts: 1,532
Registered: 5/23/05
Re: On NP Completeness and Intractability
Posted: Oct 25, 2005 1:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Randy wrote:
> I'm not a theorist, so my terminology will probably be a bit imprecise.
> But with luck, it'll help fill the gap between reality and theory...
>
> nimmi_srivastav@yahoo.com wrote:

> > 1) All the literature pertaining to intractability that I have seen
> > refers to the Turing's Halting Problem. What are other common examples
> > of intractable problems?

>
> Any task that is always solvable (decidable) and whose runtime grows
> exponentially with the size of its input set is NP Hard. In other
> words, if the input size of the task's data is N, the task's runtime is
> described by X^f(N), where X and f(N) are greater than 1 and are
> nondecreasing (they grow larger without ever growing smaller).
>

> > 2) In somewhat layman terms, what exactly is the difference between
> > NP-Hard and NP-Complete?

>
> In lay terms, there is no difference. Both describe problems whose
> solutions require runtimes that grow exponentially as their input data
> size grows linearly. "NP Complete" simply indicates that it's an "NP
> Hard" problem that has been translated into another NP Hard problem that
> is already known to be NP Complete. In other words, the problem's
> runtime grows exponentially with size and 1) we know for sure that it
> lies within the class of NP problems and 2) OUTSIDE the class of P
> problems. The NPC problem lies within that subset of NP problems that
> we are certain they can never be solved in polynomial time, that is,
> unless it turns out that *ALL* problems in NP can be solved in
> polynomial time. Right now, it looks like P is smaller subset of
> problems that lie entirely within NP.
>

> > 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard
> > problem, does that have any implication for the P=NP question?
> > [I already know that if a polynomial time algorithm is discovered for a
> > hitherto NP-Complete problem, then P=NP]

>
> In general, yes. If a problem is NP Hard (exponential), then solving it
> in polynomial time is a good sign that: 1) P=NP, or 2) the problem isn't
> really exponential after all: either it's actually in P, or it's not as
> hard as the hardest problems in NP: the NPCs.
>
> NP Complete just means that these are the hardest problems that we know
> that are always solvable. Solving any of these in polynomial time is a
> guarantee that all always-solvable-problems (all of NP) can be solved in
> polynomial time.
>
> Thus, until we prove that a given NP Hard problem is equally as hard as
> the hardest problem in NP, we can't be sure that solving it in
> polynomial time guarantees that we can solve all other solvable problems
> in polynomial time.
>

> > 4) When we refer to NP, without any qualifiers, does it imply NP-Hard?
>
> No. NP includes all of P. So all problems that always can be solved in
> polynomial time (P) also are part of NP. Problems that can be solved,
> but not always in polynomial time are called "intractable", and almost
> certainly lie in NP. These problems are NP Hard. If a NP Hard problem
> ("A") can be shown to be translated polynomially into another problem
> that is known to be NP-Complete, then we know that problem A DOES lie 1)
> in NP and 2) outside of P (it's never solvable in polynomial time), thus
> 3) we can confirm that it too is NP Complete.
>
> Colloquially, any problem that is always solvable (decidable) is
> considered to be in NP. If it is always solvable in polynomial time,
> it's in P. If it's always solvable, but not in polynomial time, it's NP
> Hard. These problems appear to be harder than polynomial (outside of
> P), but we're not certain of that (they might be polynomial sometimes).
> NP Complete means we're certain that they're solvable but that the cost
> is always exponential.
>
> Problems that are sometimes not solvable are outside P and NP. Such
> problems are called undecidable.


I read somewhere that there are problems outside NP that are solvabl,
but can be proved to need more processors than there are electrons in
the known universe. I guess we might as sell consider such problems as
undecidable in a practical sense, but decidable in formal logic.

R.G. Vickson

> They imply that some information
> that's essential to solve the problem is missing. However, undecidable
> problems are often solvable and even tractable if you can somehow find a
> way around the uncertainty. In effect, you solve a subset of the
> problem that's sufficient to serve your needs. Artificial Intelligence
> deals primarily in problems like these, as well as NP Hard problems.
> Operations Research attempts to find efficient methods to solve NP Hard
> problems, but also deals in uncertainty.
>
> Formally, NP means that a "decision problem" (solution is "yes" or "no")
> can be solved in polynomial time using a non-deterministic turing
> machine (which do not exist). It also means that the problem's solution
> can be verified in polynomial time by a deterministic turing machine
> (which do exist).
>
> For more on complexity theory:
>
> http://en.wikipedia.org/wiki/NP_%28complexity%29
>
> Randy
>

> >
> > Thanks,
> > Nimmi
> >

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