NP-complete

related topics
{math, number, function}
{rate, high, increase}
{work, book, publish}
{style, bgcolor, rowspan}

In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC) is a class of decision problems. A problem L is NP-complete if it has two properties:

  • It is in the set of NP (nondeterministic polynomial time) problems: Any given solution to L can be verified quickly (in polynomial time).
  • It is also in the set of NP-hard problems: Any NP problem can be converted into L by a transformation of the inputs in polynomial time.

Although any given solution to such a problem can be verified quickly, there is no known efficient way to locate a solution in the first place; indeed, the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a result, the time required to solve even moderately large versions of many of these problems easily reaches into the billions or trillions of years, using any amount of computing power available today. As a consequence, determining whether or not it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today.

While a method for computing the solutions to NP-complete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems. An expert programmer should be able to recognize an NP-complete problem so that he or she does not unknowingly spend time trying to solve a problem which so far has eluded generations of computer scientists. Instead, NP-complete problems are often addressed by using approximation algorithms.

Contents

Formal overview

NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine. A problem p in NP is also in NPC if and only if every other problem in NP can be transformed into p in polynomial time. NP-complete can also be used as an adjective: problems in the class NP-complete are known as NP-complete problems.

Full article ▸

related documents
Axiom schema of specification
Horner scheme
Euler–Mascheroni constant
Convergence of random variables
Preadditive category
Field extension
Linear map
Universal property
Splay tree
Projective plane
Self-organizing map
Brute-force search
Bubble sort
Euler–Maclaurin formula
Spectral theorem
Rice's theorem
Hausdorff space
Logical connective
Binary tree
Additive category
Binary heap
Planar graph
Polymorphism in object-oriented programming
Isomorphism
Constructivism (mathematics)
Chinese remainder theorem
Cauchy–Schwarz inequality
Trace (linear algebra)
Locally compact space
Transcendental number