Classes P and NP

Introduction to P and NP

P and NP are the most important complexity classes in computer science.

Simple Analogy

P problems are like:

Finding a name in phone book (binary search)
Sorting a deck of cards
Computing shortest path

NP problems are like:

Sudoku: Hard to solve, easy to check solution
Jigsaw puzzle: Hard to complete, easy to verify if done
Password cracking: Hard to find, easy to verify

The Big Question

P vs NP: Is every problem whose solution can be quickly verified also quickly solvable?

Million-dollar question! (Clay Mathematics Institute)

Class P (Polynomial Time)

Definition

P = ⋃ₖ DTIME(nᵏ)

P is the class of languages decidable in polynomial time by a deterministic TM.

Formally: L ∈ P if there exists:

Deterministic TM M
Polynomial p(n)
M decides L in time O(p(n))

Alternative Definition

L ∈ P if there exists algorithm that:

Takes input w
Runs in time polynomial in |w|
Outputs “yes” if w ∈ L, “no” otherwise

Examples in P

1. Sorting

Problem: Sort n numbers
Algorithm: Merge sort
Time: O(n log n)
In P: ✓

2. Shortest Path

Problem: Find shortest path in graph
Algorithm: Dijkstra’s algorithm
Time: O(n² log n)
In P: ✓

3. Primality Testing

Problem: Is n prime?
Algorithm: AKS algorithm (2002)
Time: O((log n)⁶)
In P: ✓

4. Linear Programming

Problem: Optimize linear objective with linear constraints
Algorithm: Ellipsoid method, Interior point
Time: Polynomial
In P: ✓

5. Graph Connectivity

Problem: Are vertices u and v connected?
Algorithm: BFS/DFS
Time: O(n + m)
In P: ✓

6. Matching

Problem: Maximum matching in bipartite graph
Algorithm: Hungarian algorithm
Time: O(n³)
In P: ✓

7. GCD

Problem: Greatest common divisor of two numbers
Algorithm: Euclidean algorithm
Time: O(log n)
In P: ✓

Why P = “Efficient”?

Philosophical:

Polynomial time = tractable
Exponential time = intractable

Practical:

n¹⁰⁰⁰ may be slow, but…
Algorithms in P often O(n²) or O(n³) in practice
Can be optimized

Robust:

Same class across reasonable models
RAM, TM, etc. differ by polynomial factor

Class NP (Non-deterministic Polynomial)

Definition 1: Non-deterministic TM

NP = ⋃ₖ NTIME(nᵏ)

NP is the class of languages decidable in polynomial time by a non-deterministic TM.

Formally: L ∈ NP if there exists:

Non-deterministic TM M
Polynomial p(n)
M decides L in time O(p(n))

Definition 2: Verifier

L ∈ NP if there exists polynomial-time verifier V such that:

w ∈ L ⟺ ∃ certificate c such that V(w, c) accepts

Certificate: “Proof” or “witness” that w ∈ L

Verifier: Checks certificate in polynomial time

Certificate length: Polynomial in |w|

Why Two Definitions Equivalent?

NTM ⇒ Verifier:

Certificate = accepting path
Verifier = follow path

Verifier ⇒ NTM:

NTM guesses certificate
Then runs verifier

Examples in NP

1. SAT (Boolean Satisfiability)

Problem: Is Boolean formula satisfiable?
Certificate: Satisfying assignment
Verify: Plug in values, evaluate (polynomial)
In NP: ✓

Example:

Formula: (x ∨ y) ∧ (¬x ∨ z)
Certificate: x=true, y=false, z=true
Verify: (T ∨ F) ∧ (F ∨ T) = T ∧ T = T ✓

2. Hamiltonian Path

Problem: Does graph have path visiting each vertex once?
Certificate: The path (sequence of vertices)
Verify: Check consecutive vertices adjacent, all visited
In NP: ✓

3. Clique

Problem: Does graph have clique of size k?
Certificate: k vertices forming clique
Verify: Check all pairs adjacent (O(k²))
In NP: ✓

4. Vertex Cover

Problem: Can k vertices cover all edges?
Certificate: Set of k vertices
Verify: Check every edge has endpoint in set (O(m))
In NP: ✓

5. Subset Sum

Problem: Does subset sum to target T?
Certificate: The subset
Verify: Add up elements (O(n))
In NP: ✓

6. Graph Coloring

Problem: Can graph be k-colored?
Certificate: Coloring of vertices
Verify: Check adjacent vertices different colors (O(m))
In NP: ✓

7. Traveling Salesman (Decision)

Problem: Is there tour of length ≤ K?
Certificate: The tour
Verify: Add up edge weights, check ≤ K
In NP: ✓

P vs NP Relationship

What We Know

P ⊆ NP: Every problem in P is in NP

Proof: If can solve in polynomial time, can verify in polynomial time

Certificate: ignore it
Verifier: just solve the problem

What We Don’t Know

P = NP or P ≠ NP?

Open problem! (50+ years)

Most believe: P ≠ NP

Evidence: Thousands of problems in NP, none proved in P or outside P

Venn Diagram

┌────────────────────────────┐
│           NP              │
│  ┌──────────────────────┐ │
│  │         P            │ │
│  │                      │ │
│  │  Sorting             │ │
│  │  Shortest path       │ │
│  │  Primality           │ │
│  │                      │ │
│  └──────────────────────┘ │
│                            │
│  SAT (NP-complete)         │
│  Hamiltonian path          │
│  Graph coloring            │
│  TSP                       │
│                            │
└────────────────────────────┘

If P = NP, inner box expands to fill outer box
If P ≠ NP, NP-complete problems stay outside P

NP-Complete Problems

Definition

Problem A is NP-complete if:

A ∈ NP (in NP)
Every problem in NP reduces to A (NP-hard)

Hardest problems in NP!

Key property: If any NP-complete problem in P, then P = NP

Polynomial-Time Reduction

A ≤ₚ B: A reduces to B in polynomial time

Definition: Computable function f such that:

w ∈ A ⟺ f(w) ∈ B

f computable in polynomial time

Use: Prove B is NP-hard

If A is NP-complete and A ≤ₚ B
Then B is NP-hard
If also B ∈ NP, then B is NP-complete

Cook-Levin Theorem

Theorem (Cook 1971, Levin 1973): SAT is NP-complete.

First NP-complete problem!

Proof Sketch

Show: Every L ∈ NP reduces to SAT

Idea:

L ∈ NP has NTM M running in time p(n)
Encode computation of M on w as Boolean formula φ
φ satisfiable ⟺ M accepts w

Variables:

Cell contents: C[i,j,s] (cell i has symbol s at time j)
State: Q[i,j,q] (at time j, head at i, state q)

Clauses:

Initial configuration
Final configuration (accept state)
Transition rules
Exactly one symbol per cell
Exactly one state

Result: φ satisfiable ⟺ w ∈ L

Size: Polynomial in |w|

Consequence: SAT is NP-complete!

Important NP-Complete Problems

1. SAT (Boolean Satisfiability)

Input: Boolean formula φ

Question: Is φ satisfiable?

Example:

φ = (x ∨ y) ∧ (¬x ∨ z) ∧ (¬y ∨ ¬z)
Solution: x=T, y=F, z=T ✓

NP-complete: Cook-Levin theorem

2. 3-SAT

Input: Boolean formula in 3-CNF (each clause has exactly 3 literals)

Question: Is formula satisfiable?

Example:

(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z)

NP-complete: Reduction from SAT

3. Hamiltonian Path

Input: Directed graph G

Question: Does G have path visiting each vertex exactly once?

Example:

1 → 2 → 3
↓   ↗   ↓
4 → 5 → 6

Path: 1→4→5→2→3→6 ✓

NP-complete: Reduction from 3-SAT

4. Hamiltonian Cycle

Input: Undirected graph G

Question: Does G have cycle visiting each vertex exactly once?

NP-complete: From Hamiltonian path

5. TSP (Traveling Salesman - Decision)

Input: Complete graph with edge weights, bound K

Question: Is there tour with total weight ≤ K?

NP-complete: From Hamiltonian cycle

6. Clique

Input: Graph G, integer k

Question: Does G have clique of size k?

Clique: Complete subgraph (all pairs connected)

NP-complete: Reduction from 3-SAT

7. Independent Set

Input: Graph G, integer k

Question: Does G have independent set of size k?

Independent set: No edges between vertices

NP-complete: Complement of clique

8. Vertex Cover

Input: Graph G, integer k

Question: Can k vertices cover all edges?

Vertex cover: Set of vertices such that every edge has at least one endpoint in set

NP-complete: Complement of independent set

9. Graph Coloring

Input: Graph G, integer k

Question: Can G be k-colored?

k-coloring: Assign one of k colors to each vertex such that adjacent vertices have different colors

NP-complete (for k ≥ 3): Reduction from 3-SAT

Note: 2-coloring is in P (bipartite check)

10. Subset Sum

Input: Set of integers S = {a₁, a₂, …, aₙ}, target T

Question: Does subset sum to T?

Example:

S = {3, 7, 2, 5, 11}
T = 10
Subset: {3, 7} ✓

NP-complete: Reduction from 3-SAT

11. Partition

Input: Set of integers S

Question: Can S be partitioned into two subsets with equal sum?

NP-complete: From subset sum

12. Knapsack (Decision)

Input: Items with weights and values, capacity W, target V

Question: Can we achieve value ≥ V with weight ≤ W?

NP-complete: From subset sum

Reduction Examples

Example: 3-SAT ≤ₚ Clique

Given: 3-SAT formula φ with m clauses

Construct: Graph G

Vertices: One vertex for each literal in each clause

Edges: Connect two vertices if:

From different clauses
Not contradictory (not x and ¬x)

Claim: φ satisfiable ⟺ G has clique of size m

Proof (⇒):

If φ satisfiable, pick one true literal per clause
These m vertices form clique (different clauses, consistent)

Proof (⇐):

If clique of size m exists, one vertex per clause
Set corresponding literals to true
No contradictions (edges only between consistent literals)
Each clause satisfied

Example: Independent Set ≤ₚ Vertex Cover

Given: Graph G, integer k

Question: Does G have independent set of size k?

Reduction: Use same G and k’ = n - k

Claim: G has independent set of size k ⟺ G has vertex cover of size n-k

Proof: S is independent set ⟺ V\S is vertex cover

Polynomial time: Identity function

Coping with NP-Completeness

If Problem is NP-Complete

Can’t hope for polynomial algorithm (unless P = NP)

Strategies:

1. Approximation Algorithms

Goal: Get close to optimal

Example: Vertex cover

Optimal: NP-complete
2-approximation: Polynomial (greedy matching)

2. Special Cases

Restrict input: May become polynomial

Example: Graph coloring

General: NP-complete
Planar graphs: Polynomial (4-color theorem)
Trees: O(n) (2-coloring)

3. Heuristics

No guarantee: But works well in practice

Example: TSP

Nearest neighbor
2-opt improvements
Simulated annealing

4. Exponential Algorithms

For small n: Exponential is okay

Example: Subset sum

Dynamic programming: O(nT)
Exponential in log T, but okay if T not huge

5. Parameterized Complexity

Fixed-parameter tractable: O(f(k)·p(n))

Example: Vertex cover

Parameter: k (cover size)
Algorithm: O(2ᵏ·n) - exponential in k, polynomial in n
Fast if k small!

Implications of P vs NP

If P = NP

Revolutionary consequences:

Cryptography collapses: RSA, etc. broken
Optimization easy: TSP, scheduling, etc. polynomial
Automated theorem proving: Math research automated
Drug design: Protein folding polynomial
AI breakthrough: Many learning problems polynomial

But: Constructive proof needed (algorithm!)

If P ≠ NP

Expected result:

Some problems inherently hard: No polynomial algorithm
Cryptography secure: Based on hardness assumptions
Search vs verification different: Fundamental asymmetry
Current practice validated: Heuristics necessary

Still: Need to prove it!

co-NP

Definition: L ∈ co-NP if L̄ ∈ NP

Equivalently: Polynomial-time verifier for non-membership

Examples:

UNSAT (unsatisfiability): co-NP
Tautology: co-NP
Primality: Both NP and co-NP (in P!)

Relationship:

P ⊆ NP ∩ co-NP

Unknown:

NP = co-NP?
P = NP ∩ co-NP?

Believed: NP ≠ co-NP

Beyond NP

NP-Hard

Definition: Problem A is NP-hard if every NP problem reduces to A

May not be in NP!

Examples:

Halting problem: NP-hard but undecidable
Optimization TSP: NP-hard but not decision problem

PSPACE

Definition: PSPACE = languages decidable in polynomial space

Known: NP ⊆ PSPACE

PSPACE-complete: TQBF (Quantified Boolean formulas)

EXPTIME

Definition: EXPTIME = languages decidable in exponential time

Known: PSPACE ⊆ EXPTIME

Strict: P ⊊ EXPTIME (proved!)

Important Exam Points

✓ P: Polynomial time (efficient)
✓ NP: Non-deterministic polynomial or verifiable in polynomial time
✓ P ⊆ NP: Known, P = NP unknown
✓ NP-complete: Hardest in NP, if one in P then all are
✓ SAT: First NP-complete (Cook-Levin)
✓ Reduction: A ≤ₚ B proves relative hardness
✓ Examples: SAT, 3-SAT, Hamiltonian path, clique, vertex cover, graph coloring
✓ Verifier: Certificate + polynomial-time checker
✓ Implications: P = NP would revolutionize CS
✓ Coping: Approximation, heuristics, special cases

Common Mistakes to Avoid

✗ Mistake 1: NP = “not polynomial”
✓ Correct: NP = “non-deterministic polynomial”

✗ Mistake 2: All NP problems exponential
✓ Correct: Many NP problems are in P (e.g., sorting)

✗ Mistake 3: NP-complete = hardest problems
✓ Correct: Hardest in NP, but PSPACE-complete harder

✗ Mistake 4: P = NP proved false
✓ Correct: Still open! Unknown for 50+ years

✗ Mistake 5: Can solve NP-complete efficiently
✓ Correct: No known polynomial algorithm (unless P = NP)

✗ Mistake 6: NP = co-NP
✓ Correct: Unknown, but believed different

Practice Questions

Q1: What is P?

Answer: Languages decidable in polynomial time.

Q2: What is NP?

Answer: Languages with polynomial-time verifiable solutions.

Q3: Is P = NP known?

Answer: No! Open problem, million-dollar prize.

Q4: What is NP-complete?

Answer: Hardest problems in NP (all NP problems reduce to them).

Q5: Give example of NP-complete problem.

Answer: SAT, 3-SAT, Hamiltonian path, clique, graph coloring, TSP.

Q6: What is Cook-Levin theorem?

Answer: SAT is NP-complete (first proved).

Q7: How to prove problem NP-complete?

Answer: Show in NP, reduce from known NP-complete problem.

Q8: Is sorting in P or NP?

Answer: P (O(n log n) algorithms exist).

Q9: What if P = NP?

Answer: Revolutionary! Crypto breaks, optimization easy, etc.

Q10: How to cope with NP-complete problem?

Answer: Approximation, heuristics, special cases, exponential for small n.

Summary

P: Polynomial time (efficient, solvable)
NP: Non-deterministic polynomial (verifiable)
P ⊆ NP: Known, P = NP? unknown
P vs NP: Million-dollar open problem
NP-complete: Hardest problems in NP
Cook-Levin: SAT first NP-complete
Examples: SAT, 3-SAT, Hamiltonian path, clique, vertex cover, graph coloring, TSP, subset sum
Reduction: A ≤ₚ B proves B at least as hard
Verifier: Certificate + polynomial checker
Implications: P = NP revolutionary, P ≠ NP expected
Coping: Approximation, heuristics, special cases
Key insight: Distinguishes easy from hard problems

P and NP classes define the frontier of tractable computation!

Classes P and NP

Introduction to P and NP

Simple Analogy

The Big Question

Class P (Polynomial Time)

Definition

Alternative Definition

Examples in P

Why P = “Efficient”?

Class NP (Non-deterministic Polynomial)

Definition 1: Non-deterministic TM

Definition 2: Verifier

Why Two Definitions Equivalent?

Examples in NP

P vs NP Relationship

What We Know

What We Don’t Know

Venn Diagram

NP-Complete Problems

Definition

Polynomial-Time Reduction

Cook-Levin Theorem

Proof Sketch

Important NP-Complete Problems

1. SAT (Boolean Satisfiability)

2. 3-SAT

3. Hamiltonian Path

4. Hamiltonian Cycle

5. TSP (Traveling Salesman - Decision)

6. Clique

7. Independent Set

8. Vertex Cover

9. Graph Coloring

10. Subset Sum

11. Partition

12. Knapsack (Decision)

Reduction Examples

Example: 3-SAT ≤ₚ Clique

Example: Independent Set ≤ₚ Vertex Cover

Coping with NP-Completeness

If Problem is NP-Complete

1. Approximation Algorithms

2. Special Cases

3. Heuristics

4. Exponential Algorithms

5. Parameterized Complexity

Implications of P vs NP

If P = NP

If P ≠ NP

co-NP

Beyond NP

NP-Hard

PSPACE

EXPTIME

Important Exam Points

Common Mistakes to Avoid

Practice Questions

Summary

Install Notes App