NP-Completeness

Noun · Development

Definitions

  1. A class of problems where: (1) a proposed solution can be verified quickly (in polynomial time), but (2) no known algorithm can find a solution quickly. All NP-complete problems are reducible to each other — solving one efficiently would solve them all. The P vs NP question (are they actually the same class?) is the biggest open problem in computer science.

    In plain English: A class of problems where checking an answer is easy but finding the answer is believed to be fundamentally slow.

    Example: "The traveling salesman problem is NP-complete — don't try to find the optimal route for 1,000 cities, use an approximation algorithm."

Related Terms