ALL (complexity)

In computability and complexity theory, ALL is the class of all decision problems.

Relations to other classes

ALL contains all of the complex classes of decision problems, including RE and co-RE.

Because there are decision problems that may or may not be undecidable due to the halting problem and the set of all Turing Machine's being higher than the amount of languages possible to process, it is impossible to solve all of these decision problems, but they are countably infinite

External links

• Complexity Zoo: Class ALL