La thèse de doctorat rédigée par Ronald Fagin à l'Université de Californie à Berkeley a établi un lien fondamental entre la logique du second ordre existentielle et la classe de complexité NP. Cette démonstration, connue aujourd'hui sous le nom de théorème de Fagin, a fourni un socle au développement de la théorie des modèles finis, façonnant la manière dont les chercheurs abordent les problèmes de décision et les machines de Turing non déterministes au sein de la complexité computationnelle.
Parcours académique
Né en 1945 à Oklahoma City, Fagin a fréquenté l'école secondaire Northwest Classen avant de poursuivre ses études au Dartmouth College. Il a achevé ses études doctorales en 1973 sous la supervision de Robert Vaught à l'Université de Californie à Berkeley. Peu après son diplôme, il a rejoint la division de recherche d'IBM, commençant son parcours au Centre de recherche Thomas J. Watson.
Contributions à la logique et aux bases de données
Fagin a été transféré à IBM Research – Silicon Valley à San Jose, en Californie, en 1975. Ses travaux englobent la théorie des bases de données et le raisonnement sur la connaissance. Au-delà de son théorème sur la complexité NP, il a démontré que la logique du premier ordre possède une loi du zéro ou un, indiquant que la probabilité qu'une phrase du premier ordre soit satisfaite par une structure à n nœuds tend vers zéro ou un lorsque n tend vers l'infini. Il a également développé des cadres théoriques pour les formes normales supérieures dans les bases de données, en particulier 4NF, 5NF et DK/NF.
Algorithmes et reconnaissance
La communauté scientifique identifie plusieurs concepts par son nom, notamment l'algorithme de Fagin pour l'agrégation de scores et l'inverse de Fagin utilisé dans l'échange de données. Tout au long de sa carrière, il a présidé des comités pour de nombreux rassemblements professionnels, tels que l'ACM Symposium on Principles of Database Systems et l'International Conference on Database Theory. Ses travaux de collaboration incluent le livre de 1995 Reasoning about Knowledge.
Vingt questions, huit minutes au chronomètre et un centile mesuré face à tous ceux qui l’ont passé. Sans inscription.
Passer le test de QI →Distinctions et affiliations
Fagin est membre de la National Academy of Sciences, de la National Academy of Engineering, de l'American Academy of Arts and Sciences et de l'IEEE. Ses récompenses incluent le prix Gödel de 2014, le prix Alonzo Church de 2020 et le prix W. Wallace McDowell de 2012. Il a également reçu un doctorat honoris causa de l'Université Paris-Dauphine.
En bref
- Naissance : 1945, Oklahoma City - Éducation : Dartmouth College, Université de Californie à Berkeley - Employeur : IBM - Théorème clé : Théorème de Fagin - Prix sélectionné : Prix Gödel (2014) - Affiliation professionnelle : Membre de l'ACM - Domaine notable : Théorie des modèles finis
Questions fréquentes
### Qu'est-ce que le théorème de Fagin ?
Il indique qu'un problème de décision est exprimable en logique du second ordre existentielle si et seulement s'il est résoluble par une machine de Turing non déterministe en temps polynomial.
### Où Fagin a-t-il mené ses recherches ?
Il a passé sa carrière au sein de la division de recherche d'IBM, principalement chez IBM Research – Silicon Valley.
