Re: NP - Hard -- Approximation algos

From: Foo Bar (foobar965_at_hotmail.com)
Date: 04/05/05


Date: 5 Apr 2005 10:55:31 -0700


"jumpstart" <jumpstart101@gmail.com> wrote in message news:<1112594935.719424.87720@f14g2000cwb.googlegroups.com>...

<snip>
>
> Regarding "This problem is known to be NP-hard."
> (In first page,2nd Column, 2nd Paragraph, 1st line)
>
> I would be happy to have answers based on my sub-questions.
>
> 1. What is NP- hard?

A NP-hard problem is a problem such that every problem in NP poly-time
reduces to it. A NP-complete problem is a problem in NP such that
every problem in NP poly-time (Karp-) reduces to it.

The distinction is important since NP is often defined as containing
only decision problems. For example, with this definition of NP,
Traveling Salesman is in NP, but phrased as "_Is_ there a route
shorter than k for this graph?" (NP-complete). The constructive
version (called Minimum Traveling Salesman), phrased as "Give me a
route shorter than k for this graph!", is NP-hard.

> 2. Why this problem is NP - hard?

Why? Because every problem in NP poly-time reduces to it. Why is
Traveling Salesman NP-complete? Same reason.

> 3. How to prove this is NP- hard?

Find a polynomial time reduction from a known NP-hard (or NP-complete)
problem to this problem.

You might try and look it up in Garey & Johnson (problem ND30). There
might be a reference to a proof there. If you are interested in
approximation algorithms, the other references are probably helpful.
Oh, and the problem is also called "Shortest Weight-Constrained Path".

What exactly is it you are interested in? The NP-hardness proof? A
FPTAS for the problem? Something else?

Also, be aware the some of the answers you have gotten from other
posters are partially incorrect...

/FB



Relevant Pages

  • Re: NP-hardness
    ... completeness proof (reduction from a known NP-complete decision problem ... NP-hard problem to it) and that it is NP. ... Optimization problem which is NP hard but not NP-complete like minimum ... We'll solve SAT by finding the minimum reprezentation of BF. ...
    (sci.math)
  • Re: Can someone give me an example of this type of problem?
    ... > I have seen the definition of NP-Complete as a problem that is both NP-Hard ... > and in NP and began wondering about problems that didn't fit this definition. ... is apparently harder than any NP-complete problem. ...
    (comp.theory)
  • Re: NP-complete and NP-Hard?
    ... There are NP-hard problems that are not in NP, ... Yes, NP-complete ... the trivial languages. ...
    (comp.theory)
  • Re: NP-complete and NP-Hard?
    ... I though that NP-complete is the intersection of ... NP and NP-hard. ... Isn't this question equivalent to P ?= NP? ...
    (comp.theory)