History of Complexity theory in computation

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

Changed: 20,21c20

The set P is the set of decision problems that can be solved in polynomial time. The set NP is the set of decision problems whose
solution can be verified in polynomial time. The question of whether P is the same set as NP is the most important open question in all of theoretical computer science. There is even a $1,000,000 prize for solving it. (See Complexity classes P and NP and oracles).

The set P is the set of decision problems that can be solved in polynomial time. The question of whether P is the same set as NP is the most important open question in all of theoretical computer science. There is even a $1,000,000 prize for solving it. (See Complexity classes P and NP and oracles).

	Revision 6 . . December 14, 2001 3:30 pm by AxelBoldt [reverting: NP is defined in the previous paragraph already]
	Revision 5 . . December 14, 2001 1:47 pm by (logged).93.53.xxx
	Revision 4 . . December 10, 2001 12:06 am by AxelBoldt [Reverting. Little Guru, stop your idiotic edits.]
	Revision 3 . . December 10, 2001 12:05 am by Little guru [added [[data mining]] to definition]
	Revision 2 . . (edit) December 7, 2001 6:55 am by (logged).112.129.xxx [example of a complement]
	Revision 1 . . December 6, 2001 7:21 am by (logged).202.117.xxx