
Re: On NP Completeness and Intractability
Posted:
Oct 25, 2005 2:05 PM


In sci.math Randy <joe@burgershack.com> wrote: > I'm not a theorist, so my terminology will probably be a bit imprecise.
Unfortunately you are being very imprecise. Unfortunately this is an easy topic to be imprecise about, but one which you need to be precise about. You seem to be using a nonstandard definition of NPcomplete and NPhard and as a result most of your answers are incorrect according to the standard definitions.
> 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.
No, NPComplete means that the problem is in NP and it is NPhard. You can prove a problem is NPhard by reducing it to another NPhard problem. There is no need to use an NPcomplete problem to show that a problem is NPhard.
> 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.
No, we do not know that it is outside the class of P problems, nor do we know that the runtime is necessarily exponential.
> 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.
If a problem in NPhard then we know that it is as hard as the hardest problems in NP. That is the definition of NPhard. If you find a polynomial time solution for an NPhard problem then P=NP. There is no maybe about it.
> 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.
No, there are plenty of problems "harder" than NPcomplete problems that are solvable, assuming of course that P!=NP. For example, any NPhard problem that is not NPcomplete. Of course proving that a problem is not NPcomplete is not trivial. I do not recall if there are any NPhard problems that have been definitely proven to not be NPcomplete.
> 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.
By definition an NPhard problem is as hard as the hardest problem in NP. That is the definition of NP.
<snip>
As I said earlier, your definitions of NPcomplete and NPhard are nonstandard, and as a result most of your answers are incorrect according to the standard definitions.
Stephen

