En anonym läsare skriver: "På eftermiddagen 4 maj 1971 i Stouffer s Somerset Inn i Shaker Heights, Ohio, presenterade Steve Cook hans stoc papper som bevisar att Satisfierbarhet är NP-komplett och tautologi är NP-svårt." De satser tyder på att tautologi är en bra kandidat för en intressant inte ställa in [P] och jag känner att det är värt att spendera stora ansträngningar att försöka bevisa denna hypotes. Ett sådant bevis skulle vara ett stort genombrott i komplexitetsteori. " Och på så sätt Cook formulerade vad som var snart att kallas P mot NP problem. Resten är historia. Här är 1971 års stoc Program (det fanns 143 deltagare) och vad som helig mark ser ut idag. "
Läs mer i denna historia på Slashdot.
Inga kommentarer:
Skicka en kommentar