Un lettore anonimo scrive "Nel pomeriggio del 4 maggio 1971, nel Stouffer's Somerset Inn a Shaker Heights, Ohio, Steve Cook, ha presentato la sua carta stoc dimostrando che Soddisfacibilità è NP-completo e tautologia è NP-hard. 'I teoremi suggeriscono che tautologia è un buon candidato per un set non interessante in [P] e sento che è la pena di spendere un notevole sforzo cercando di dimostrare questa congettura. Tale prova sarebbe un importante passo avanti nella teoria della complessità. ' E così Cook formulato quello che stava per essere chiamato il problema P versus NP. Il resto è storia. Ecco il programma stoc 1.971 (erano 143 partecipanti) e cosa che terra sacra come appare oggi. "
Per saperne di più di questa storia a Slashdot.
Nessun commento:
Posta un commento