
Re: On NP Completeness and Intractability
Posted:
Oct 25, 2005 1:52 PM


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 > > NPHard and NPComplete? > > 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 NPHard > > 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 NPComplete 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 alwayssolvableproblems (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 NPHard? > > 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 NPComplete, 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 nondeterministic 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

