Computational complexity theory
Keywords: | computation, efficiency, security, algorithms, computability |
Date: |
- 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
- For example, the complexity class "P" is bounded by the constraint "polynomial time", i.e.