Computational complexity theory -

Back to notes

Computational complexity theory

Keywords: computation, efficiency, security, algorithms, computability
  • A realm of study that seeks to identify categories of algorithms and classify them according to their efficiency
    • efficiency is measured with regard to resource usage, i.e. CPU/memory load and time
    • parallels theoretical computer science fields like "algorithmic analysis" and "computability theory"
    • differs from algorithmic analysis in that computational complexity theory is more general and, rather than seeking to analyze the efficiency of a particular algorithm, seeks to quantify and qualify all of the possible algorithms that could be used to solve a particular problem
      • this particularly includes very difficult problems that cannot be solved efficiently
    • the classes used to categorize problems by complexity (known as "complexity classes") are generally bounded by some time/space constraint
      • For example, the complexity class "P" is bounded by the constraint "polynomial time", i.e. O(poly(n)), meaning that any problems which require more time/space than this will graduate to the next class
      • More on complexity classes