La tesi di dottorato scritta da Ronald Fagin presso l'Università della California, Berkeley, ha stabilito un legame fondamentale tra la logica del secondo ordine esistenziale e la classe di complessità NP. Questa dimostrazione, nota ora come teorema di Fagin, ha fornito una base per lo sviluppo della teoria dei modelli finiti, plasmando il modo in cui i ricercatori affrontano i problemi di decisione e le macchine di Turing non deterministiche all'interno della complessità computazionale.
Formazione accademica
Nato nel 1945 a Oklahoma City, Fagin ha frequentato la Northwest Classen High School prima di proseguire gli studi al Dartmouth College. Ha completato i suoi studi di dottorato nel 1973 sotto la supervisione di Robert Vaught presso l'Università della California, Berkeley. Poco dopo la laurea, è entrato a far parte della divisione di ricerca di IBM, iniziando la sua attività presso il Thomas J. Watson Research Center.
Contributi alla logica e ai database
Fagin si è trasferito presso IBM Research – Silicon Valley a San Jose, in California, nel 1975. Il suo lavoro comprende la teoria dei database e il ragionamento sulla conoscenza. Oltre al suo teorema sulla complessità NP, ha dimostrato che la logica del primo ordine possiede una legge dello zero o dell'uno, indicando che la probabilità che una frase del primo ordine sia soddisfatta da una struttura con n nodi converge a zero o uno man mano che n tende all'infinito. Ha inoltre sviluppato quadri teorici per forme normali superiori nei database, nello specifico 4NF, 5NF e DK/NF.
Algoritmi e riconoscimento
La comunità scientifica identifica diversi concetti attraverso il suo nome, tra cui l'algoritmo di Fagin per l'aggregazione dei punteggi e la funzione inversa di Fagin utilizzata nello scambio di dati. Nel corso della sua carriera, ha ricoperto il ruolo di presidente di comitato per numerosi incontri professionali, come l'ACM Symposium on Principles of Database Systems e l'International Conference on Database Theory. Il suo lavoro di collaborazione include il libro del 1995 Reasoning about Knowledge.
Venti domande, otto minuti di orologio e un percentile misurato su tutti quelli che l’hanno fatto. Senza registrazione.
Fai il test del QI →Riconoscimenti e affiliazioni
Fagin è membro della National Academy of Sciences, della National Academy of Engineering, dell'American Academy of Arts and Sciences e dell'IEEE. I suoi riconoscimenti includono il Premio Gödel del 2014, il Premio Alonzo Church del 2020 e il Premio W. Wallace McDowell del 2012. Ha inoltre ricevuto una laurea honoris causa dall'Università Paris Dauphine.
Sintesi
- Nato: 1945, Oklahoma City - Formazione: Dartmouth College, Università della California, Berkeley - Datore di lavoro: IBM - Teorema chiave: Teorema di Fagin - Premio selezionato: Premio Gödel (2014) - Affiliazione professionale: Fellow ACM - Settore di rilievo: Teoria dei modelli finiti
Domande frequenti
### Cos'è il teorema di Fagin?
Esso stabilisce che un problema di decisione è esprimibile nella logica del secondo ordine esistenziale se e solo se è risolvibile da una macchina di Turing non deterministica in tempo polinomiale.
### Dove ha condotto le sue ricerche Fagin?
Ha trascorso la sua carriera all'interno della divisione di ricerca di IBM, principalmente presso IBM Research – Silicon Valley.
