Re: NP-hardness

Thanks for reply. Anyway I want the sample proof for NP-hardness proof
of optimization problems which are NP hard not NP complete even if it
should be converted to decision problem.
Proginoskes wrote:
sara wrote:
Thanks, I was looking for "optimization" problems which are NP hard and
not NP complete proof. Actually I want their NP hardness proofs.

NP hard problems, NP-complete problems, and problems in NP are not
optimization problems; they are decision problems, where the only
outputs are YES and NO.

Optimization problems can be converted into decision problems by asking
about "thresholds"; i.e., instead of finding the cheapest TSP route,
the NP-type problem is "Is there a TSP route with cost <= C?"

--- Christopher Heckman

Proginoskes wrote:
sara wrote:
Hi All,

I am looking for a proof for a sketchy proof of NP hardness of an
Optimization problem which is NP hard but not NP-complete like minimum
traveling salesman problem.

The Halting Problem is NP-hard but not in NP. (See Wikipedia:
http://en.wikipedia.org/wiki/Np-hard , 2nd paragraph of "Examples")

If you go to Google Groups, you can search for threads like this in
sci.math.

The best seems to be "problems that are NP hard but not NP?"
http://groups.google.com/group/sci.math/browse_frm/thread/5314bb737413198d/2ca01dcc2e93626b?lnk=gst&q=%22np-hard%22+%22not+np-complete%22&rnum=1#2ca01dcc2e93626b

.

Relevant Pages

  • Re: NP-hardness
    ... Actually I want their NP hardness proofs. ... NP hard problems, NP-complete problems, and problems in NP are not ... Optimization problems can be converted into decision problems by asking ...
    (sci.math)
  • Re: Decision Problem and Optimization Problem
    ... Often you can convert these into decision problems ("is the nth digit ... > a lower bound and a upper bound, if we can solve the corresponding ... some optimization problems have unbounded solution spaces. ...
    (comp.theory)
  • Decision Problem and Optimization Problem
    ... Church-Turing thesis. ... A book say ALL problems are classfied into decision problems or ... optimization problems. ... a lower bound and a upper bound, if we can solve the corresponding ...
    (comp.theory)
  • Re: Decision Problem and Optimization Problem
    ... > Deokhwan Kim wrote: ... Are there any problems that can't be converted into decision problems? ... >> a lower bound and a upper bound, if we can solve the corresponding ... > some optimization problems have unbounded solution spaces. ...
    (comp.theory)