1985 · Theory & algorithms

A map of computational difficulty

Reductions showed that many practical problems share the same hard core.

Richard Karp

1985Turing Award

Visual guide

The prize, pictured

Open full-size ↗Download poster ↓中文版海报 ↗

A map of computational difficulty: Reductions showed that many practical problems share the same hard core. — Original AI-generated infographic by Curionode. Read the text version below for the full explanation.

Read the poster text

Identify
State a computational problem.
Translate
Reduce a known hard problem to it.
Connect
Place it on a map of complexity.

Understanding problem structure guides the choice between exact methods, approximation, heuristics and specialised algorithms.

A hardness result is about a general class of inputs; many special cases can still be solved efficiently.

01 · The idea

In everyday language

Richard Karp connected a broad collection of combinatorial problems through polynomial-time reductions. If an efficient exact algorithm existed for one NP-complete problem, these translations could transfer that power to the others. His work also developed efficient algorithms for network flow and other optimisation tasks.

Why it matters

Understanding problem structure guides the choice between exact methods, approximation, heuristics and specialised algorithms.

02 · The people

Who brought the idea to life?

Richard Karp

Richard Karp helped explain why many important optimization problems resist efficient exact solutions. His work showed that a broad collection of combinatorial problems are NP-complete by connecting them through polynomial-time reductions. At Berkeley, he also developed algorithms and investigated approaches to difficult problems. His research gave computer scientists a shared framework for distinguishing tractable tasks from problems whose apparent difficulty requires different strategies.

Read the biography ↗

03 · Read further