Computational complexity theory

• 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 ↗