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 .
One important idea is that determining the existence of a solution to a problem, and verifying that a solution is correct are different problems and can belong to different complexity classes. In fact, verifying that a solution is correct is easier than finding the solution itself.
Intuitively, this should be true. For example, for a Hamiltonian path problem, we can easily verify whether a path satisfies the property (we just check if every node is visited once by the path). But finding the path itself is an NP-complete problem.
Important classes:
- P (polynomial time) — the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine, i.e., class of languages for which membership can be decided quickly.
- NP (non-deterministic polynomial time) — the class of languages that have polynomial time verifiers, i.e., class of languages for which we can verify quickly.
- It relies on non-deterministic computer models (i.e., a Turing machine), which have the ability to “pursue” an unbounded number of computational sequences in parallel, i.e., they can examine multiple possible sequences. Because they’re non-deterministic, there isn’t a single sequence they are required to take, so they can take paths with some probability.
Sub-pages
Resources
- Introduction to the Theory of Computation, by Michael Sipser
- Computers and Intractability: A Guide to the Theory of NP-Completeness, by Michael R. Garey and David S. Johnson