What does NP stand for?

NP means nondeterministic polynomial time. Equivalently, a problem is in NP if a proposed solution can be checked in polynomial time, even if finding one seems hard. The traveling salesman route below a given length is easy to verify once given but apparently hard to discover.

How do you prove a new problem is NP-complete?

You show two things: that the problem is in NP, so candidate solutions are checkable quickly, and that some known NP-complete problem reduces to it in polynomial time. The reduction transfers the known hardness, placing the new problem among the hardest in NP.

NP-Completeness and Reductions

An NP-complete problem is one of the hardest in the class NP, in the sense that every NP problem reduces to it efficiently, so that solving any single NP-complete problem quickly would solve them all.

Намерете тема с PaperMindСкороFind papers & topics

Tools & resources

Изтегляне на слайдове

Learn & explore

ВидеоСкоро

Definition

A problem is NP-complete if it lies in NP and every problem in NP reduces to it by a polynomial-time reduction; such problems are the maximally hard members of NP, equivalent to one another up to efficient transformation.

Scope

This topic covers the class NP of problems verifiable in polynomial time, polynomial-time many-one reductions, the Cook–Levin theorem establishing satisfiability as NP-complete, Karp's catalogue of NP-complete combinatorial problems, and the methodology of proving new problems NP-complete by reduction from known ones.

Core questions

What does it mean for a problem to be among the hardest in NP?
How does the Cook–Levin theorem identify a first NP-complete problem?
How are reductions used to prove that a new problem is NP-complete?
Why does the NP-completeness of one problem have implications for thousands of others?

Key theories

Cook–Levin theorem: Boolean satisfiability is NP-complete because the computation of any polynomial-time verifier can be encoded as a satisfiability instance, providing the foundational complete problem from which others are derived.
Karp reductions and the web of NP-complete problems: Karp showed that twenty-one natural problems, from graph coloring to the traveling salesman decision problem, are NP-complete by polynomial-time reductions, launching the practice of establishing hardness through a growing network of reductions.

Clinical relevance

NP-completeness is the practical diagnostic of intractability: once a problem in scheduling, logistics, design, or verification is shown NP-complete, engineers stop seeking a guaranteed-fast exact algorithm and turn to approximation algorithms, heuristics, integer-programming solvers, or restrictions that make the problem tractable.

History

Cook proved satisfiability NP-complete in 1971, and Levin independently obtained equivalent results in the Soviet Union. In 1972 Karp demonstrated twenty-one further NP-complete problems, revealing the phenomenon's pervasiveness and making NP-completeness the central tool for diagnosing computational hardness.

Key figures

Stephen Cook
Leonid Levin
Richard Karp

Seminal works

cook1971
karp1972

Frequently asked questions

What does NP stand for?: NP means nondeterministic polynomial time. Equivalently, a problem is in NP if a proposed solution can be checked in polynomial time, even if finding one seems hard. The traveling salesman route below a given length is easy to verify once given but apparently hard to discover.
How do you prove a new problem is NP-complete?: You show two things: that the problem is in NP, so candidate solutions are checkable quickly, and that some known NP-complete problem reduces to it in polynomial time. The reduction transfers the known hardness, placing the new problem among the hardest in NP.