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

---

Relevant Wikipedia Articles:

the concept- decision problem

related field(s)- theory of computation

potential real-world examples-

---

/Discussion?