Course contentsShow
← Computer Science
Lesson 1904 of 2,87243. Complexity TheoryFree lesson

Examples of Problems in NP

Study classic NP problems: SAT, Hamiltonian path, subset sum, and graph coloring with their certificates.

Examples of Problems in NP

You'll learn the classic problems that define the NP complexity class and see why they're important for understanding computational limits.

What Makes a Problem "In NP"?

Remember that a problem is in NP if, given a solution candidate (a certificate), you can verify whether it's correct in polynomial time. Think of it like a jigsaw puzzle: solving it might take hours, but checking if someone else solved it correctly is much faster—you just look at the completed picture.

Classic NP Problems

SAT (Boolean Satisfiability)

Given a Boolean formula like (x OR y) AND (NOT x OR z), is there an assignment of true/false values that makes the whole formula true?

Certificate: An assignment like x=true, y=false, z=true
Verification: Plug in the values and check if the formula evaluates to true—takes polynomial time.

Hamiltonian Path

Does a graph contain a path that visits every vertex exactly once?

Certificate: A sequence of vertices like [A, B, D, C, E]
Verification: Check that consecutive vertices are connected by edges and all vertices appear once—polynomial time.

Subset Sum

Given numbers like {3, 5, 8, 12} and a target 13, is there a subset that sums to the target?

Certificate: A subset like {5, 8}
Verification: Add the numbers and check if they equal 13—polynomial time.

Graph Coloring

Can you color a graph's vertices with k colors so no adjacent vertices share a color?

Certificate: A color assignment for each vertex
Verification: Check each edge to ensure its endpoints have different colors—polynomial time.

Why These Matter

These problems represent fundamentally different computational challenges, yet they all share the property that verification is much easier than finding a solution from scratch.

Key Takeaway: Classic NP problems like SAT, Hamiltonian path, subset sum, and graph coloring are "easy to verify, hard to solve"—you can quickly check a proposed solution certificate in polynomial time, even though finding one might require exponential time.