NP Decision Task
(Redirected from NP Task)
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.
- 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):
- 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,"...