How fast do running times grow?
How long is that, at a billion steps per second?
Hover the chart to read exact step counts.
Big-O, in Sipser's words
f(n) = O(g(n)) if there are c > 0 and n0 such that f(n) ≤ c·g(n) for every n ≥ n0 (Definition 7.2). Constants and lower-order terms don't matter: 5n3 + 2n + 22 = O(n3).
f(n) = o(g(n)) if f(n)/g(n) → 0 (Definition 7.5). For example n log n = o(n2), and every polynomial nk is o(2n).
P is the class of languages decidable in polynomial time, O(nk) for some k, on a single-tape deterministic Turing machine (Definition 7.12).
Measure a Turing machine's running time
SAT: checking is easy, finding is hard
A formula in conjunctive normal form: clauses in parentheses joined by ∧.
Click a variable to flip it between 0 and 1.
3SAT reduces to CLIQUE (Theorem 7.32)
P, NP and NP-completeness
NP is the class of languages with a polynomial-time verifier: a yes-answer comes with a certificate that can be checked quickly (Definitions 7.18–7.19). For SAT the certificate is a satisfying assignment, and checking it is one pass over the formula.
A language is NP-complete if it is in NP and every language in NP reduces to it in polynomial time (Definition 7.34). SAT is NP-complete (the Cook–Levin theorem, Theorem 7.37), and so is 3SAT. The reduction on this page shows CLIQUE is NP-complete too: a polynomial-time algorithm for CLIQUE would give one for 3SAT, and then P = NP. Whether P = NP is still unknown.