Wikipedia:Wpc/decision problem

Definition: A computational problem which requires a yes/no answer.

Equivalently, a computational problem for which the goal is to determine whether an input string belongs to a particular formal language.

Generalizations:

• computational problem

Specializations: computability:

• undecidable problem[?]
• decidable problem

difficulty:

• computationally tractable decision problem (is in P)
• nondeterministically computationally tractable decision problem (is in NP)
• computationally intractable decision problem (is not in P)

Involved in:

• decidable language

related field(s)- theory of computation

potential real-world examples-

See also : Wpc