<<Up     Contents

Redirected from Wpc/nondeterministically computationally tractable decision problem

Table of contents 1 Also known as: 2 Definition: 3 Generalizations: 4 Specializations: 5 Involved in: 6 Relevant Wikipedia Articles:

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