History of Complexity classes P and NP/Talk

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

Added: 18a19,20

But then my original statement stands: if we find a non-constructive proof of P=NP, then we still wouldn't have a polynomial algorithm for NP problems, since a polynomial algorithm has to stop after p(n) steps. --AxelBoldt

	Revision 10 . . December 20, 2001 12:06 am by AxelBoldt
	Revision 9 . . December 19, 2001 10:45 am by LC
	Revision 8 . . December 18, 2001 2:38 pm by AxelBoldt
	Revision 7 . . December 18, 2001 8:47 am by LC
	Revision 6 . . December 17, 2001 1:45 pm by AxelBoldt
	Revision 5 . . December 17, 2001 12:31 pm by LC [Algorithm that's polytime iff P=NP]
	Revision 4 . . December 17, 2001 12:00 pm by AxelBoldt
	Revision 3 . . December 17, 2001 11:18 am by LC [Nonconstructive P=NP proof with no algorithm isn't possible]
	Revision 2 . . December 17, 2001 5:57 am by AxelBoldt [Consequences of solving P=NP]
	Revision 1 . . December 17, 2001 5:41 am by (logged).117.133.xxx