Re: NP-complete and NP-Hard?

On Mon, 20 Jun 2005, Torkel Franzen wrote:

> 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.
!!!!!!!!!!!!!!!!!!!!!
That would be severals years after his death!

Hypocoristiquement,
Jym.
.

Relevant Pages

  • Re: NP-complete and NP-Hard?
    ... > polynomial time? ... An NP-complete problem is a problem that is completely ... while an NP-hard problem is a problem that is hardly ... 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)
  • Re: P=NP Proof Published at CERN
    ... any NP-complete problem in polynomial time will be ... fame, the Clay prize money, and perhaps even ...
    (sci.math)
  • Re: P = NP, background study?
    ... In response to Casey Hawthorne...it's already been proven that if you ... can solve one NP-complete problem in polynomial time, ... then there would be no NP-complete problem that is not solvable ... Or between discrete mathematics and flagrant mathematics. ...
    (comp.theory)
  • Re: NP completeness
    ... There is no NP-complete problem to which the answer is always "yes." ... solving some problem in propositional logic, ... you *think* you have a polynomial time algorithm to ... time algorithm that generates the solution to a NP-complete problem, ...
    (sci.math)