P, NP, and NP-Completeness

P vs NP — The Million-Dollar Question

P = problems that computers can SOLVE quickly (polynomial time) NP = problems where you can VERIFY a solution quickly (polynomial time)

Analogy: - Finding a 1000-piece jigsaw puzzle solution = HARD (may take hours) - Verifying if a given arrangement is correct = EASY (just look and check)

NP problems are "easy to check, hard to find."

Formal Definitions

P:  {L | L decided by a deterministic TM in O(n^k) time for some k}
NP: {L | L decided by a non-deterministic TM in O(n^k) time}
  = {L | ∃ a polynomial-time VERIFIER V: w ∈ L iff ∃ certificate c, V(w,c) = accept}

P ⊆ NP  (if you can solve quickly, you can also verify quickly)

Is P = NP? Unknown. Most believe P ≠ NP but no proof exists. This is the biggest open problem in mathematics.

NP-Complete — The Hardest Problems in NP

X is NP-complete iff:
  1. X ∈ NP        (easy to verify)
  2. X is NP-hard  (every NP problem reduces to X in polynomial time)

NP-hard: at least as hard as any NP problem (but may not even be in NP)
NP-complete = NP ∩ NP-hard

Visual:

        NP
       /    \
      P    NP-Complete ← hardest in NP
            |
         NP-Hard (may be outside NP, e.g., Halting Problem)

If you find a polynomial algorithm for ANY NP-complete problem → P = NP → ALL NP problems become polynomial!

Proving NP-Completeness — The Template

To show problem X is NP-complete:

Step 1: Show X ∈ NP
  "Given a candidate solution (certificate), I can verify it in polynomial time."

  Example for Vertex Cover:
  Certificate = a set S of k vertices
  Verify: check every edge has at least one endpoint in S → O(|E|) time ✓

Step 2: Show X is NP-hard
  Pick a KNOWN NP-complete problem Y.
  Show Y ≤p X (polynomial reduction from Y to X).
  "If I could solve X, I could also solve Y."

Classic NP-Complete Problems

Problem	Description
SAT	Does a boolean formula have a satisfying assignment?
3-SAT	SAT with exactly 3 literals per clause
Vertex Cover	Can k vertices cover all edges in a graph?
Clique	Does graph have a clique (complete subgraph) of size k?
Independent Set	Does graph have an independent set of size k?
Hamiltonian Cycle	Is there a cycle visiting every vertex exactly once?
TSP (decision)	Is there a tour of all cities with total cost ≤ k?
Subset Sum	Does a subset of numbers sum to target T?
Graph 3-Coloring	Can vertices be coloured with 3 colours (no two adjacent = same)?

Problems IN P (easy!)

Sorting:                O(n log n)
Shortest path:          Dijkstra O(E log V), Bellman-Ford O(VE)
MST:                    Kruskal/Prim O(E log V)
Linear programming:     polynomial
2-SAT:                  O(n) via SCC   ← KNOW THIS!
2-coloring (bipartite): O(V+E) BFS/DFS
Max matching in bipartite: O(E√V) (Hopcroft-Karp)

GATE trap: 2-SAT is in P. 3-SAT is NP-complete. Know the boundary!

Relationships Between NP-Complete Problems

Clique ↔ Independent Set:
  G has k-clique ⟺ complement(G) has k-independent set
  (complement graph: flip edges and non-edges)

Vertex Cover ↔ Independent Set:
  S is a vertex cover of G ⟺ V-S is an independent set
  (if all edges are covered by S, then V-S has no edges between its nodes)

Chain: 3-SAT ≤p Independent Set ≤p Vertex Cover ≤p Clique

Quick Check

Q1. Problem X is in NP and 3-SAT ≤p X. Is X NP-complete? Answer: Yes! X ∈ NP (given) and 3-SAT reduces to X (making X NP-hard). Both conditions met.

Q2. Is 2-coloring of graphs in P or NP-complete? Answer: P — it is equivalent to checking if a graph is bipartite, solvable in O(V+E) using BFS/DFS.

Q3. A graph has 5 vertices. Vertex cover of size 3 = {v1,v2,v3}. The independent set is? Answer: V - {v1,v2,v3} = {v4,v5}. Size 2. (Vertex cover complement = independent set.)

Key Points