Also known as:
NP problem
Definition:
A
decision problem for which there exists a [nondeterministic algorithm]
? that solves it in [polynomial time]
?.
Equivalently, a
decision problem for which there exists an algorithm
? to validate a purported answer in [polynomial time]
?, given the right information.
Equivalently, a member of complexity class
NP.
Generalizations:
- [nondeterministically computationally tractable problem]?
- decidable problem (remove time requirement)
Specializations:
Involved in:
Relevant Wikipedia Articles:
the concept-
related field(s)- complexity theory
potential real-world examples-
/Discussion
?
![[Home]](wikipedia.png)
Wpc/nondeterministically computationally tractable decision problem