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

• Theory of Computation Course
• Calculus of Computation Textbook, Section 2.6 (Decidability and Complexity)
• Gallier Logic Book, Section 3.3.5
• Theory of Computation Courses and Books
• Complexity Theory: A Modern Approach, Chapter on NP and NP completeness