History of NP-Complete

	Revision 6 . . December 6, 2001 7:26 am by (logged).202.117.xxx
	Revision 5 . . August 25, 2001 11:24 pm by AxelBoldt [cook's theorem, move alternative reduction to the end.]

---

Difference (from prior major revision) (no other diffs)

Changed: 1c1

In complexity theory, the complexity class NP-complete is the set of problems that are the hardest problems in NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve an NP-complete problem quickly, then you can use that algorithm to solve all NP problems quickly. (See Complexity classes P and NP).

In complexity theory, the complexity class NP-complete is the set of problems that are the hardest problems in NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve an NP-complete problem quickly, then you can use that algorithm to solve all NP problems quickly. (See Complexity classes P and NP).