# Computational Complexity Theory

- subfield of theoretical computer science
- primary goal "is to classify and compare the practical difficulty of solving problems about finite combinatorial objects" source
- "Complexity helps determine the difficulty of a problem, often measured by how much time and space (memory) it takes to solve a particular problem. For example, some problems can be solved in polynomial amounts of time and others take exponential amounts of time, with respect to their input size." source
- complexity theory proposes "a formal criterion for what it means for a mathematical problem to be
*feasibly decidable*– i.e. that it can be solved by a conventional Turing machine in a number of steps which is proportional to a polynomial function of the size of its input. The class of problems with this property is known as P – or*polynomial time*... P can be formally shown to be distinct from certain other classes such as EXP – or*exponential time*...complexity class known as NP – or*non-deterministic polynomial time*– consisting of those problems which can be correctly decided by some computation of a non-deterministic Turing machine in a number of steps which is a polynomial function of the size of its input. A famous conjecture – often regarded as the most fundamental in all of theoretical computer science – states that P is also properly contained in NP – i.e. P⊊NP." source

## Real World Implications

- can be important to algorithm design and analysis
- often described in big-O notation
- knowing if an algorithm runs in polynomial time vs exponential time can tell us how efficient an algorithm is

## Decision Problems

- "Such a problem corresponds to a set X in which we wish to decide membership." source
- "...problems that can be answered with a "yes" or a "no." For example, "is this number prime?", "does this graph have a hamiltonian path?""is there an assignment of variables to the equation such that a set of constraints are satisfied?"" source
- famous problems: Travelling Salesperson Problem, 3SAT, minimum spanning tree problems, primality testing
- can be simulated on computational models like Turing machines