Computational complexity theory is a sub-field of theoretical computer science and mathematics. The idea is that computational problems (those we can solve with an algorithm) can be sorted into classes depending on their resource usage.
Complexity classes
Complexity classes are a set of problems that can be solved with a specific amount of computational time. Recall, for a function , we have time complexity .
Non-deterministic computer models have the ability to “pursue” an unbounded number of computational sequences in parallel.
- P (polynomial time)
- NP (non-deterministic polynomial time)
Sub-pages
Resources
- Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael R. Garey and David S. Johnson