History of NP

	Revision 8 . . (edit) December 6, 2001 7:24 am by (logged).202.117.xxx
	Revision 7 . . August 20, 2001 9:03 pm by AxelBoldt [polytime -> polynomial time]
	Revision 6 . . August 20, 2001 8:25 am by (logged).105.27.xxx

---

Difference (from prior major revision) (minor diff, author diff)

Changed: 1c1

In complexity theory, NP is the set of decision problems solvable in polytime on a nondeterministic Turing machine. Or, equivalently, YES answers are checkable in polytime on a deterministic Turing machine. See Complexity classes P and NP and NP-Complete.

In complexity theory, NP is the set of decision problems solvable in polynomial time on a nondeterministic Turing machine. Or, equivalently, YES answers are checkable in polynomial time on a deterministic Turing machine. See Complexity classes P and NP and NP-Complete.