Examples of Problems in NP
You'll learn: How classic NP problems like SAT, Hamiltonian Path, and Clique demonstrate the verifiable-in-polynomial-time nature of the NP class.
The Core Idea
Now that you understand NP as the class of problems where solutions can be verified quickly (in polynomial time), let's look at the famous problems that live there. Each has a common pattern: given a candidate solution (called a "certificate"), you can check whether it's correct efficiently, even though finding that solution might be extremely hard.
Classic NP Problems
Boolean Satisfiability (SAT)
Problem: Given a boolean formula like (x OR y) AND (NOT x OR z), is there an assignment of true/false to variables that makes it true?
Certificate: An assignment like x=true, y=false, z=true
Verification: Simply plug in the values and evaluate—takes polynomial time in the formula's size.
Hamiltonian Path
Problem: Does a graph have a path visiting every vertex exactly once?
Certificate: A sequence of vertices like [A, B, C, D, E]
Verification: Check that consecutive vertices are connected by edges and all vertices appear once—polynomial in the number of vertices.
Clique
Problem: Does a graph contain a subset of k vertices where every pair is connected?
Certificate: A set of k vertices
Verification: Check all pairs in the subset have edges between them—polynomial time.
Analogy
Think of NP problems like a massive jigsaw puzzle. Finding the solution (placing all pieces) might take forever, but checking if someone's completed puzzle is correct takes just a quick glance.
Key Takeaway: Classic NP problems like SAT, Hamiltonian Path, and Clique share a crucial property—verifying a proposed solution is fast (polynomial time), even though finding one may not be.