|
Equivalently, a computational problem for which the goal is to determine whether an input string belongs in a particular formal language. |
|
Equivalently, a computational problem for which the goal is to determine whether an input string belongs to a particular formal language. |
|
solvability: * [unsolvable decision problem]? * [solvable decision problem]? |
|
computability: * [undecidable problem]? * decidable problem |
|
* computationally tractable decision problem * computationally intractable decision problem |
|
* computationally tractable decision problem (is in P) * nondeterministically computationally tractable decision problem (is in NP) * computationally intractable decision problem (is not in P) |
|
Nothing yet |
|
* decidable language |
![[Home]](wikipedia.png)