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

"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