REFERENCE SHEET

P, NP & completeness

Ask what can be computed efficiently after establishing that it can be computed at all.

Before this Turing machines, deciders & recognizers, Asymptotics & recurrences, Boolean logic, circuits & satisfiability

A ≤ₚ B and B ∈ P ⇒ A ∈ P

Definitions

P

Decision languages decidable by a deterministic Turing machine in time polynomial in the encoded input length.

NP

Decision languages with polynomial-length certificates whose validity can be checked by a deterministic polynomial-time verifier. Equivalently, nondeterministic polynomial time.

NP-hard and NP-complete

B is NP-hard if every language in NP polynomial-time many-one reduces to B. It is NP-complete if it is also in NP.

Key theorems

Basic containment

P⊆NP: a verifier can ignore the certificate and run the polynomial-time decider.

Cook–Levin theorem

Boolean satisfiability is NP-complete. In particular, polynomial-time SAT would imply P=NP.

Completeness transfer

To prove B NP-complete, prove B∈NP and reduce a known NP-complete language A to B with a polynomial-time membership-preserving transformation.

Notable applications

Optimization strategy

NP-hardness motivates approximation, parameterized algorithms, special cases, or exact exponential methods rather than a promised general polynomial-time solution.

Verification vs discovery

A proposed solution may be quick to check even when no efficient general discovery algorithm is known.

Work it out

Try before revealing

01 / Verify

For CLIQUE, the input is a graph and k. Describe a certificate and verifier for a yes-instance.

Hint

List the proposed vertices and check all pairs.

Solution

The certificate lists k distinct vertices. Check membership, distinctness, and the existence of all k(k−1)/2 edges. This is polynomial in the graph encoding length (reject immediately if k exceeds the vertex count).

02 / Reduce

Reduce CLIQUE to INDEPENDENT SET.