Algorithmic or computational complexity
The computational complexity of an algorithm is an asymptotic estimate of how the algorithm's use of resources (running time / memory) scales with the size of its input. It can be considered as an extension of Computability theory, by saying not only which algorithms are possible, but how fast they run.
https://en.wikipedia.org/wiki/Computational_complexity_theory
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Algorithmic%20Complexity/complexity.html
Pseudo-polynomial time: if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it. That is because numerical number is related to number of bits (digits in binary), , by .
P vs. NP and the Computational Complexity Zoo
Big O notation
Similar to Order notation used in Asymptotic analysis, but we ignore multiplicative constants..
Complexity cases
Time complexity classes
PTIME. Algorithms that run in polynomial time.
NP (nondeterministic polynomial). Problems with efficiently recognizable solutions.
Problems that can be solved in polynomial times by non-deterministic Turing machines.
Problems that can be described by an existential second-order formula.
NP-completeness. NP reduction.
Computaional unsolvability, like Hilbert's 10th problem.
- #P: problems of counting/enumerating the number of solutions to an NP problem.
- #P complete.
Turns out that #P is at least as powerful as NP, and BQP.
Computational complexity of Randomized algorithms
BPP = P ?
Computational complexity of Quantum algorithms
https://blog.computationalcomplexity.org/2018/06/bqp-not-in-polynomial-time-hierarchy-in.html?m=1
BQP ?
The importance of these complexity classes derives from the additional fact that they are useful for classifying naturally occurring problems. Many problems that arise are mental search problems or their corresponding counting problems. It just so happens that when we come across a new task that we would like to have solved, if we cannot find a polynomial time algorithm for it, then more often than not, we can prove that it is complete in (i.e., is a hardest member of) its class NP or #P. Logically they could fall in between, but for reasons we do not understand, they rarely do. For this reason this theory gives useful guidance as to the practical solvability of new problems as they arise.
Kolmogorov complexity
See Algorithmic information theory
Statistical physics
Determining computational complexity from characteristic ‘phase transitions’. See also Statistical physics and inference
https://www.wikiwand.com/en/Structural_complexity_theory