NP Decision Task

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

An NP Decision Task is a computational decision task where a yes answer can be verified in polynomial time.



References

2013

2009

  • (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The status of the P versus NP problem.” In: Communications of the ACM, 52(9).
    • QUOTE: The collection of problems that have efficiently verifiable solutions is known as NP (for "Nondeterministic Polynomial-Time,"...