NP Decision Task

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

• AKA: Nondeterministic Polynomial-Time Task.
• Context:
  • It can be solved by a nondeterministic Turing Machine in a number of steps that is a polynomial function of the size of the input.
• Example(s):
  • a P Decision Task.
  • a Linear Programming Task (Khachian, 1979).
  • an Exact Bayesian Inference Task.
  • an Integer Factorization.
• See: Efficiently Verifiable Solution, NP-Hard Task, NP-Complete Task.

---

---

References

2013

• http://mathworld.wolfram.com/NP-Problem.html
  • A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine.

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,"...

---