NP-completeness

Polynomial time refers to an amount of time that is considered "quick" for a deterministic algorithm to check a single solution, or for a nondeterministic Turing machine to perform the whole search.

More precisely, each input to the problem should be associated with a set of solutions of polynomial length, the validity of each of which can be tested quickly (in polynomial time),[2] such that the output for any input is "yes" if the solution set is non-empty and "no" if it is empty.

The complexity class of problems of this form is called NP, an abbreviation for "nondeterministic polynomial time".

While a method for computing the solutions to NP-complete problems quickly remains undiscovered, computer scientists and programmers still frequently encounter NP-complete problems.

NP-complete problems are often addressed by using heuristic methods and approximation algorithms.

NP-complete problems are in 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 non-deterministic Turing machine.

[4] A consequence of this definition is that if we had a polynomial time algorithm (on a UTM, or any other Turing-equivalent abstract machine) for

At the 1971 STOC conference, there was a fierce debate between the computer scientists about whether NP-complete problems could be solved in polynomial time on a deterministic Turing machine.

John Hopcroft brought everyone at the conference to a consensus that the question of whether NP-complete problems are solvable in polynomial time should be put off to be solved at some later date, since nobody had any formal proofs for their claims one way or the other.

The Clay Mathematics Institute is offering a US$1 million reward (Millennium Prize) to anyone who has a formal proof that P=NP or that P≠NP.

Note that this diagram is misleading as a description of the mathematical relationship between these problems, as there exists a polynomial-time reduction between any two NP-complete problems; but it indicates where demonstrating this polynomial-time reduction has been easiest.

At present, all known algorithms for NP-complete problems require time that is superpolynomial in the input size.

greedy coloring algorithm used for graph coloring during the register allocation phase of some compilers, a technique called graph-coloring global register allocation.

Because most RISC machines have a fairly large number of general-purpose registers, even a heuristic approach is effective for this application.

in polynomial time, one could write a program that calls this subroutine and solves

If one defines the analogue to NP-complete with Turing reductions instead of many-one reductions, the resulting set of problems won't be smaller than NP-complete; it is an open question whether it will be any larger.

Whether under these types of reductions the definition of NP-complete changes is still an open problem.

Some NP-Complete problems such as SAT are known to be complete even under polylogarithmic time projections.

[8] According to Donald Knuth, the name "NP-complete" was popularized by Alfred Aho, John Hopcroft and Jeffrey Ullman in their celebrated textbook "The Design and Analysis of Computer Algorithms".

He reports that they introduced the change in the galley proofs for the book (from "polynomially-complete"), in accordance with the results of a poll he had conducted of the theoretical computer science community.

[9] Other suggestions made in the poll[10] included "Herculean", "formidable", Steiglitz's "hard-boiled" in honor of Cook, and Shen Lin's acronym "PET", which stood for "probably exponential time", but depending on which way the P versus NP problem went, could stand for "provably exponential time" or "previously exponential time".

[12] Viewing a decision problem as a formal language in some fixed encoding, the set NPC of all NP-complete problems is not closed under: It is not known whether NPC is closed under complementation, since NPC=co-NPC if and only if NP=co-NP, and since NP=co-NP is an open question.