# Computational Complexity Theory Computational complexity theory provides a formal mechanism to classify how hard problems are to solve using computation, typically in terms of how much time is needed to solve the problem. ## P: Polynomial-time computation - Polynomial-time computation is an idealized definition of 'easy' problems defined as - An algorithm runs in polynomial time if there is some polynomial function $p$ (e.g., $p(n)=10+n^{2}$ ) such that for inputs of size $n$, it takes at most $p(n)$ time steps. - Intuition: input get larger, algo takes longer, but not much more so. - Examples: sorting, multiplication ## NP: Non-deterministic polynomial-time computation - A problem is in the class NP if it asks for a solution (that can be described with a polynomial-length string), and given the problem input and a candidate solution, checking if the solution is correct can be done in polynomial time. - Intuition: finding a needle in a haystack, and the needle is easy to recognize once you have found it. - Examples: solving a sudoku is difficult but checking if it's correct is pretty easy, job scheduling, traveling salesman problem ## P vs. NP problem - Does being able to quickly recognize correct answers (NP) also mean there's also a quick way to find them (P)? ## NP-completeness - NP-completeness is a way to classify problems as "as hard as anything in NP". - At the core, many NP problems are the same problems called NP-complete problems. A program for computing any NP-complete problems could be used to any problems in NP. - NP-completeness indicates that a problem involves nontrivial combinatorial search. - Some typical properties of combinatorial search problems: - An exponential-size search space - Often the task is to find some solution in this space - Examples: - Traveling salesperson problem - Reaching some set of goals with limited resources - Fault diagnosis - A reduction translates inputs of problem $A$ to inputs of problem $B$ and solutions of $B$ to those of $A$ - Intuition: solving $A$ using an algorithm for $B$ - A problem $B$ in NP is NP-complete if there is a polynomial-time reduction from each problem in NP to $B$. ## NP-hard - The problems that are at-least as hard as NP-complete are called NP-hard. Verifying the solutions of these problems are themselves NP. --- ## References 1. Complexity zoo: https://complexityzoo.net/Complexity_Zoo 2. Nice summary video: https://www.youtube.com/watch?v=YX40hbAHx3s