50 años de complejidad computacional: Hao Wang y la teoría de la computación

Por • 30 jul, 2022 • Sección: Educacion

Nick Zhang

Si el innovador artículo de Turing de 1936 sentó las bases de la teoría de la computación (ToC), no es exagerado decir que el artículo de Cook de 1971, «La complejidad de los procedimientos de prueba de teoremas», [4] ha sido pionero en el estudio de la complejidad computacional. Entonces, la complejidad computacional, como campo de investigación independiente, tiene ahora 50 años (2021) si datamos del artículo de Cook. Este año coincide con el centenario del mentor de Cook, Hao Wang, uno de los lógicos más importantes. Este documento rastrea el origen de la complejidad computacional y, mientras tanto, intenta resolver el papel instrumental que jugó Wang en el proceso.

arXiv:2206.05274v1 [cs.GL]
General Literature (cs.GL)

Post to Twitter

Escribe un comentario