La tesis doctoral escrita por Ronald Fagin en la Universidad de California en Berkeley estableció un vínculo fundamental entre la lógica de segundo orden existencial y la clase de complejidad NP. Esta demostración, conocida ahora como el teorema de Fagin, proporcionó una base para el desarrollo de la teoría de modelos finitos, moldeando la forma en que los investigadores abordan los problemas de decisión y las máquinas de Turing no deterministas dentro de la complejidad computacional.
Antecedentes académicos
Nacido en 1945 en Oklahoma City, Fagin asistió a la escuela secundaria Northwest Classen antes de continuar sus estudios en el Dartmouth College. Completó sus estudios de doctorado en 1973 bajo la supervisión de Robert Vaught en la Universidad de California en Berkeley. Poco después de graduarse, se unió a la División de Investigación de IBM, comenzando su trayectoria en el Centro de Investigación Thomas J. Watson.
Contribuciones a la lógica y las bases de datos
Fagin se trasladó a IBM Research – Silicon Valley en San José, California, en 1975. Su trabajo abarca la teoría de bases de datos y el razonamiento sobre el conocimiento. Más allá de su teorema sobre la complejidad NP, demostró que la lógica de primer orden posee una ley de cero o uno, indicando que la probabilidad de que una sentencia de primer orden sea satisfecha por una estructura de n nodos converge a cero o uno a medida que n tiende al infinito. También desarrolló marcos teóricos para formas normales superiores en bases de datos, específicamente 4NF, 5NF y DK/NF.
Algoritmos y reconocimiento
La comunidad científica identifica varios conceptos a través de su nombre, incluido el algoritmo de Fagin para la agregación de puntuaciones y la inversa de Fagin utilizada en el intercambio de datos. A lo largo de su carrera, ha ejercido como presidente de comités en numerosas reuniones profesionales, como el Simposio de la ACM sobre Principios de Sistemas de Bases de Datos y la Conferencia Internacional sobre Teoría de Bases de Datos. Su trabajo de colaboración incluye el libro de 1995 Reasoning about Knowledge.
Veinte preguntas, ocho minutos de reloj y un percentil medido frente a todos los que la han hecho. Sin registro.
Hacer la prueba de CI →Honores y afiliaciones
Fagin es miembro de la Academia Nacional de Ciencias, la Academia Nacional de Ingeniería, la Academia Estadounidense de Artes y Ciencias y el IEEE. Sus galardones incluyen el Premio Gödel de 2014, el Premio Alonzo Church de 2020 y el Premio W. Wallace McDowell de 2012. También recibió un doctorado honoris causa de la Universidad Paris Dauphine.
Datos clave
- Nacimiento: 1945, Oklahoma City - Educación: Dartmouth College, Universidad de California en Berkeley - Empleador: IBM - Teorema clave: Teorema de Fagin - Premio seleccionado: Premio Gödel (2014) - Beca profesional: Miembro de la ACM - Campo notable: Teoría de modelos finitos
Preguntas frecuentes
### ¿Qué es el teorema de Fagin?
Identifica que un problema de decisión se puede expresar en lógica de segundo orden existencial si y solo si puede ser resuelto por una máquina de Turing no determinista en tiempo polinómico.
### ¿Dónde realizó Fagin su investigación?
Desarrolló su carrera dentro de la División de Investigación de IBM, principalmente en IBM Research – Silicon Valley.
