NP-Complete Decision Task

From GM-RKB
(Redirected from NP-complete problem)
Jump to navigation Jump to search

An NP-Complete Decision Task is an NP decision task X for which it is possible to reduce any other NP problem Y to X in polynomial time (if we can solve Y quickly if we know how to solve X quickly).



References

2015

2013

2011

2009

  • (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The status of the P versus NP problem.” In: Communications of the ACM, 52(9).
    • So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.

       We call the very hardest NP problems (which include Partition into Triangles, Clique, Hamiltonian Cycle and 3-Coloring) "NP-complete," that is, given an efficient algorithm for one of them, we can find an efficient algorithm for all of them and in fact any problem in NP. Steve Cook, Leonid Levin, and Richard Karp10, 24, 27 developed the initial theory of NP-completeness that generated multiple ACM Turing Awards.

2005