Lab for Automated Reasoning and Analysis LARA

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

sav08/computational_complexity.txt · Last modified: 2010/02/22 01:13 by vkuncak
© EPFL 2018 - Legal notice