Computational intractability, artificial intelligence, and the Cold War

Aquesta tesi té com a objectiu explicar el descobriment de la intractibilitat computacional fora de la intel·ligència artificial durant la Guerra Freda. La intractibilitat computacional és un concepte descobert en la lògica matemàtica que explica si un algorisme informàtic no pot resoldre un problema particular en un temps raonable (P) o no (NP). La intractabilitat computacional va ser formalitzada pel científic informàtic Stephen Cook al seu famós article “The complexity of theorem proving procedures” (1971). Cook va poder formalitzar la seva distinció P/NP gràcies al treball del director doctoral, el filòsof Hao Wang. Durant la dècada de 1960, Wang estava desenvolupant un programa que podia resoldre els teoremes de lògica matemàtica proposats per Bertrand Russell i Alfred North Whitehead a la seva “Principia mathematica” (1910-1913). Usant el mètode Herbrand-Skolem, Wang va poder provar tots els teoremes de lògica matemàtica proposats per Russell i Whitehead. El seu treball va obtenir millors resultats que el “Logic Theorist” (LT) d’Hebert Simon i Allen Newell. El LT va poder demostrar només 38 teoremes dels Principia. Tot i que el Programa P de Wang era més poderós que l’LT, el seu treball va ser ignorat per la primera comunitat d’intel·ligència artificial. Per què va passar aquesta situació? La resposta pot estar a les limitacions de la Guerra Freda imposades a la investigació científica. La República Popular de la Xina i els EUA estaven en tensió política perquè cada país defensava ideologies diferents. Mentre la Xina era comunista, els Estats Units eren capitalistes. Tots dos bàndols desconfiaven l’un de l’altre. En aquest sentit, es van imposar restriccions polítiques als ciutadans vists com una amenaça als interessos nacionals. En el cas dels EUA, els professionals i acadèmics xinesos van ser vistos amb desconfiança per part del govern dels EUA. Per això no tenien accés a les ciències relacionades amb la seguretat nacional i els interessos militars dels EE.UU. UU. La intel·ligència artificial primerenca ...