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

Examples of Problems in NP

Exploring SAT, Hamiltonian Path, Clique, and other classic NP problems with their verification algorithms.

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.