Np-complete - Dictionary Definition and Overview

Np-complete :

(NPC, Nondeterministic Polynomial time complete) A set or property of computational decision problems which is a subset of NP (i.e. can be solved by a nondeterministic Turing Machine in polynomial time), with the additional property that it is also NP-hard. Thus a solution for one NP-complete problem would solve all problems in NP. Many (but not all) naturally arising problems in class NP are in fact NP-complete.

There is always a polynomial-time algorithm for transforming an instance of any NP-complete problem into an instance of any other NP-complete problem. So if you could solve one you could solve any other by transforming it to the solved one.

The first problem ever shown to be NP-complete was the satisfiability problem. Another example is Hamilton's problem.

See also computational complexity, halting problem, Co-NP, NP-hard.

http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/np/)">(http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/).

[Other examples?]

(1995-04-10)

Example Usage of Np-complete
	bash_dot_org: Show the following problem is Np-complete: The dominating-set problem: given a graph G and an integer k… http://bash.org/?22135
	BrianEnigma: @substitute It's only of those classic Np-complete problems they teach you at university, like the Traveling Salesman and the Knapsack.
	twitfics: "Show me the Good list," Santa booms, and is stunned at the result. "My goodness," he says at last. "I forgot this problem was Np-complete."

Example Usage of Np-complete