Um leitor anónimo escreve "Na tarde de 04 de maio de 1971, em Somerset a Stouffer's Inn em Shaker Heights, Ohio, Steve Cook apresentou o seu documento STOC provando que Satisfação é NP-completos e Tautologia é NP-hard." Os teoremas sugerem que Tautologia é uma boa candidata para um conjunto não é interessante em [P] e eu sinto que é o esforço vale a pena gastar considerável tentando provar esta conjectura. Tal prova seria um grande avanço na teoria da complexidade. " E assim Cook formulou o que estava prestes a ser chamado de P versus NP problema. O resto é história. Aqui está o Programa STOC 1971 (eram 143 pessoas) e que esse solo sagrado parece hoje ".
Leia mais desta história em Slashdot.
Nenhum comentário:
Postar um comentário