Re: NP-complete and NP-Hard?

yijun_lily@xxxxxxxxx writes:

> Is NP-complete and NP-Hard problem a problem that can't be solved in
> polynomial time (i.e.)?

An NP-complete problem is a problem that is completely
non-predictable, while an NP-hard problem is a problem that is hardly
non-predictable. This was all establish by Turing in the sixties.


.

Relevant Pages

  • Re: On NP Completeness and Intractability
    ... An NP-Complete problem is proven to be in NP, ... > an NP-hard problem in not proven to be in NP (it might or it might not be ... >> 3) If a polynomial time algorithm is discovered for a hitherto NP-Hard ...
    (comp.theory)
  • Re: On NP Completeness and Intractability
    ... polynomic time to this class. ... An NP-Complete problem is proven to be in NP, an NP-hard problem in not proven to be in NP. ...
    (comp.theory)
  • Re: NP-complete and NP-Hard?
    ... > I don't quite understand NP-Complete and NP-Hard problem, ... NP is the class of problems that can be solved in polynomial time (in ... that you need exponential time to solve an NP problem - there might be ...
    (comp.theory)
  • Re: NP-complete and NP-Hard?
    ... >> polynomial time? ... > An NP-complete problem is a problem that is completely ... Jym. ... Prev by Date: ...
    (comp.theory)
  • If P==NP how to solve the Prime Factorization problem?
    ... I am looking for information on "if a polynomial time algorithm exists ... factorization ends up in P. ... for any other NP-Complete problem. ...
    (comp.theory)