Wikipedia:Wpc/decision problem

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

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

---

Relevant Wikipedia Articles:

the concept- decision problem

related field(s)- theory of computation

potential real-world examples-

---

/Discussion

See also : Wpc