P, NP and NP-completeness
Definitions and key theorems about P, NP, NP-hard and NP-complete, how to show membership in NP, and a standard polynomial-time reduction (3-SAT to CLIQUE) with worked exam-style answers.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Computational complexity theory tells an engineer which problems can be solved quickly (in practice) and which probably cannot. Knowing P, NP and NP-completeness helps when you must choose algorithms, approximate solutions, or prove that no fast algorithm is likely to exist for a problem in software, hardware design, verification or optimization.
Key ideas
Polynomial time: An algorithm or TM runs in polynomial time if its running time is O(n^k) for some constant k, where n = |input|.
P (polynomial time): Definition — P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. Exact statement used in exams: P = ⋃_{k≥1} TIME(n^k), where TIME(t(n)) is the class of languages decidable in O(t(n)) time by a deterministic TM. Assumption: time measured with respect to input length n; standard encoding of inputs.
NP (nondeterministic polynomial time): Two equivalent definitions commonly used in exams:
- Machine definition: NP is the set of decision problems solvable by a nondeterministic Turing machine in polynomial time.
- Verifier/certificate definition: NP is the set of decision problems L for which there exists a polynomial p(·) and a deterministic polynomial-time verifier V such that x ∈ L iff there exists a certificate y with |y| ≤ p(|x|) and V(x,y) = accept. You must be able to show the equivalence of these two definitions: nondeterministic choices correspond to guessing the certificate y and then verifying deterministically. Also know co-NP: co-NP = { L | L^c ∈ NP }; P ⊆ NP ∩ co-NP, and whether NP = co-NP is open.
Polynomial-time many-one reduction (≤_p): Definition — Language A ≤_p B if there exists a polynomial-time computable function f such that for every string x, x ∈ A iff f(x) ∈ B. The function f is called a reduction or transformation. Assumption: f is computed by a deterministic TM in polynomial time.
NP-hard: Definition — A language H is NP-hard if for every L ∈ NP, L ≤_p H. Intuitively H is at least as hard as every problem in NP (not required to be in NP).
NP-complete: Definition — A language C is NP-complete if (i) C ∈ NP and (ii) C is NP-hard. Equivalently, C ∈ NP and every L ∈ NP reduces to C in polynomial time.
Important theorem (exam style, exact statement): If there exists any NP-complete language C that is in P, then P = NP. Proof idea: For any L ∈ NP, L ≤_p C and C ∈ P, so L ∈ P by composing polynomial-time reduction and polynomial-time decision of C; thus NP ⊆ P and P ⊆ NP always holds, giving equality.
Cook–Levin theorem (statement): SAT (the Boolean satisfiability problem) is NP-complete. Exact exam-level statement: SAT ∈ NP, and for every L ∈ NP there exists a polynomial-time reduction from L to SAT. Assumptions: SAT is the problem of deciding satisfiability of a Boolean formula given in propositional logic; standard encoding of TM computation into Boolean formula. Proof sketch often asked: encode the accepting computation tableau of a nondeterministic polynomial-time TM on input x into a Boolean formula that is satisfiable iff the TM accepts x. This is technical: construct variables for tape symbols, head position, and machine state at each time step and clauses to enforce correct transitions and initial/final conditions.
Typical exam derivation: show a concrete problem is NP-complete by two steps: (1) show it is in NP (give verifier), (2) give a polynomial-time reduction from a known NP-complete problem (e.g., 3-SAT or SAT) to it, and prove correctness of the reduction both ways.
Diagram you should draw when explaining reductions like 3-SAT → CLIQUE: draw k groups of nodes (one group per clause). In group i draw nodes labelled by the three literals of clause i. Draw no edges within a group; draw edges between nodes in different groups if and only if the literals are not complementary (i.e., not a variable and its negation, x and x̄). Then indicate k-clique selection picks one literal per clause consistent across clauses.
Formulas
P = ⋃_{k≥1} TIME(n^k) — P is the union of deterministic time classes TIME(n^k); n = input length; applies when using single-tape TM model or equivalent multi-tape with polynomial overhead.
NP = { L | there exists polynomial p and deterministic TM V such that for all x: x ∈ L ⇔ ∃y, |y| ≤ p(|x|) and V(x,y) accepts in poly(|x|) time } — defines NP via verifier; sizes in symbols; applies under standard polynomial-time notion.
A ≤_p B ⇔ ∃ function f computable in polynomial time such that ∀x: x ∈ A ⇔ f(x) ∈ B — polynomial-time many-one reduction; f computed by deterministic TM in O(n^k) time.
If C is NP-complete and C ∈ P then P = NP — consequence of closure under polynomial-time composition.
Worked examples
Example 1 — Show CLIQUE ∈ NP (model exam answer) Problem statement: CLIQUE = { (G,k) | G is an undirected graph having a clique of size k }. Answer steps:
- Certificate: a list of k vertices v1,..,vk claimed to form a clique.
- Verifier V(G,k,certificate) checks: (a) certificate length ≤ k·log|V(G)| (or simply k numbers encoded), (b) for every pair (vi,vj) check that edge (vi,vj) ∈ E(G). There are k(k−1)/2 checks.
- Each check is done in O(1) or O(log n) depending on representation; overall time is polynomial in |G| and k.
- If a clique exists then some certificate makes V accept; if no clique then no certificate can make V accept. Thus CLIQUE ∈ NP. Final answer: CLIQUE is in NP with the given polynomial-time verifier.
Example 2 — Show 3-SAT ≤_p CLIQUE (standard reduction) (model exam answer) Problem: Given a 3-CNF formula φ with clauses C1, C2, ..., Ck, construct graph G and integer k' such that G has a clique of size k' iff φ is satisfiable. Construction steps:
- For each clause Ci = (ℓ_{i1} ∨ ℓ_{i2} ∨ ℓ_{i3}), create three vertices labelled (i,1), (i,2), (i,3) corresponding to the three literals.
- Add an edge between vertex (i,a) and (j,b) whenever i ≠ j and the literals ℓ_{i,a} and ℓ_{j,b} are not complementary (i.e., not x and ¬x for the same variable x).
- Set k' = k (number of clauses). Proof of correctness:
- If φ is satisfiable, take a satisfying assignment and for each clause pick one literal that is true; its corresponding vertex from each clause forms a set of k vertices. Because chosen literals are true under the same assignment, no two chosen vertices correspond to complementary literals, so all cross-clause pairs are connected by edges. Hence the set is a k-clique.
- If G has a k-clique, it must pick exactly one vertex from each clause group (because there are no edges within a group). The literals corresponding to these k vertices cannot contain complementary pairs, so assign their variables to make those literals true and assign arbitrary values to remaining variables; this satisfies φ. Complexity: Construction is polynomial (O(k^2) pair checks). Thus 3-SAT ≤_p CLIQUE, so CLIQUE is NP-hard; combined with Example 1 shows CLIQUE is NP-complete.
Example 3 — Short proof: If any NP-complete problem is in P then P = NP
- Let C be NP-complete and assume C ∈ P.
- For any L ∈ NP, since C is NP-hard, there is polynomial-time f with x ∈ L iff f(x) ∈ C.
- Decide L in polynomial time: on input x compute f(x) in polynomial time, then decide f(x) ∈ C in polynomial time. Composition is polynomial, so L ∈ P.
- Thus NP ⊆ P. Since P ⊆ NP always, P = NP. This is the standard exam argument.
Common mistakes
- Giving a reduction but not proving both directions (⇐ and ⇒) of equivalence between instances.
- Using reductions that are not computable in polynomial time (must explicitly argue time bound).
- In graph reductions: forgetting to forbid edges inside the same clause group when doing 3-SAT → CLIQUE (causes false cliques).
- Claiming SAT is in P or asserting P = NP; confusing NP-hard with NP-complete (NP-complete requires membership in NP).
For your exam
Types of questions:
- Definitions: exact definitions of P, NP, NP-hard, NP-complete, polynomial reduction.
- Short notes: explain Cook–Levin theorem sketch, difference between NP and co-NP.
- Derivations: prove P ⊆ NP and the consequence 'if an NP-complete ∈ P then P=NP'.
- Reductions: give a full polynomial-time reduction from a known NP-complete problem (3-SAT, SAT) to another problem (CLIQUE, VERTEX-COVER) and prove correctness.
- Diagrams: draw gadget constructions (e.g., graph with clause groups for CLIQUE reduction); label groups, vertices, and edges. What a full-marks answer includes:
- Precise definitions (bold terms if asked), explicit construction of the reduction function f, time-complexity argument showing f is polynomial-time, and rigorous iff proof for correctness (two directions). For membership proofs give certificate and deterministic verifier and argue polynomial time.
Quick check
- Give the verifier-based definition of NP in one sentence.
- In the 3-SAT → CLIQUE reduction, why do we set k' = number of clauses?
- State the consequence of finding a polynomial-time algorithm for any NP-complete problem. Answers: 1) NP = set of languages for which membership can be verified in polynomial time given a polynomial-size certificate. 2) Because the clique must pick one true literal per clause, so size equals number of clauses. 3) If any NP-complete problem is in P then P = NP (all NP problems become polynomial-time solvable).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?