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.
While ALL contains all decision problems, it does not necessarily cover space complexities such as PSPACE and EXPSPACE because it merely covers the problems enclosed in those classes, not the class itself.
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