P vs NP Overview

Math for CS · Axiom Academy

The most important open problem in computer science Complexity theory studies decision problems — problems with a yes/no answer. Every optimization problem has a decision version: Optimization: "What is the shortest route visiting all cities?" Decision: "Is there a route visiting all cities with total distance ?" We classify decision problems by how much time (as a function of input size n ) they require. Informally: problems we can solve efficiently . Examples: Sorting: Is this array sorted? — O(n) Shortest path: Is there a path from s to t with weight ? — O(n^2) via Dijkstra 2-SAT: Is this 2-CNF formula satisfiable? — O(n) via implication graphs Primality: Is n prime? — via AKS algorithm Matching: Does this bipartite graph have a perfect matching? — O(n^ 2.5 ) P is the class of "tractable" problems — problems we consider feasible to solve in practice. Equivalently: problems solvable in polynomial time by a nondeterministic Turing machine (one that can "guess" the right answer and verify it). SAT: Given a Boolean formula, is it satisfiable? Certificate: a satisfying assignment. Verify by plugging in — O(n) . Hamiltonian cycle: Does the graph have a cycle visiting every vertex exactly once? Certificate: the cycle. Verify by checking it's valid — O(n) . Subset sum: Is there a subset summing to k ? Certificate: the subset. Verify by adding — O(n) . We know . The million-dollar question is whether the reverse holds:

This is the written version of the interactive lesson above. See the full Math for CS course.