← Lessons

quiz vs the machine

Silver1120

Algorithms

NP Completeness Intro

Why a whole family of problems seems easy to check but hard to solve.

5 min read · intro · beat Silver to climb

Two kinds of difficulty

Some problems are easy to solve; others are merely easy to check. The class P holds problems solvable quickly, in time bounded by a polynomial in the input size. The class NP holds problems whose proposed answers can be verified quickly, even if finding them seems hard.

What NP complete means

A problem is NP complete when it sits in NP and is also among the hardest in NP, meaning every other NP problem can be transformed into it efficiently. If anyone ever solved one NP complete problem quickly, every NP problem would fall too. Classic examples include boolean satisfiability, Hamiltonian path, and the traveling salesman decision.

The great open question

Nobody knows whether P equals NP. Most researchers believe they differ, so that NP complete problems have no fast algorithm. But this remains unproven, one of the deepest open questions in all of computing.

Why it matters in practice

Recognizing that a task is NP complete is liberating, not defeating. It tells you to stop hunting for a perfect fast algorithm and instead reach for approximation, heuristics, special cases, or smaller inputs.

Key idea

NP complete problems are the hardest in NP, easy to verify but with no known fast solver, and solving any one quickly would solve them all.

Check yourself

Answer to earn rating on the learn ladder.

1. What characterizes problems in the class NP?

2. What follows if one NP complete problem gets a fast algorithm?