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

In computational complexity theory, the complexity class NPcomplete (abbreviated NPC or NPC) is a class of decision problems. A problem L is NPcomplete 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 NPhard 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 NPcomplete 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 NPcomplete problems using a reasonable amount of time remains undiscovered, computer scientists and programmers still frequently encounter NPcomplete problems. An expert programmer should be able to recognize an NPcomplete 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, NPcomplete problems are often addressed by using approximation algorithms.
Contents
Formal overview
NPcomplete 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. NPcomplete can also be used as an adjective: problems in the class NPcomplete are known as NPcomplete 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 
Selforganizing map 
Bruteforce 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 objectoriented programming 
Isomorphism 
Constructivism (mathematics) 
Chinese remainder theorem 
Cauchy–Schwarz inequality 
Trace (linear algebra) 
Locally compact space 
Transcendental number 
