Wikipedia:Wpc/nondeterministically computationally tractable decision problem

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:

• computationally tractable decision problem (require determinism)
• NP-complete problem[?]

Involved in:

• NP

related field(s)- computational complexity theory

potential real-world examples-

See also : Wpc