# Computational Complexity

Problem = languages = sets of bitstrings (give yes/no answer to each input)

- Time and space complexity
- Complexity of an algorithm
- Time complexity of a problem: if there exists an algorithm for this problem
- Space complexity
- Deterministic and non-deterministic complexity
- Undecidable and Enumerable (Semidecidable) problems

Some important classes of problems:

- P, NP, coNP, PSPACE, EXPTIME, NEXPTIME, elementary

Ackerman's function

## More Information

- Calculus of Computation Textbook, Section 2.6 (Decidability and Complexity)
- Gallier Logic Book, Section 3.3.5