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