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 ]
 Randy Posts: 19 Registered: 12/13/04
Re: On NP Completeness and Intractability
Posted: Oct 25, 2005 1:36 PM

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