Die von Ronald Fagin an der University of California, Berkeley, verfasste Doktorarbeit stellte eine grundlegende Verbindung zwischen der existenziellen Logik zweiter Stufe und der Komplexitätsklasse NP her. Dieser Beweis, der heute als Fagins Satz bekannt ist, bildete ein Fundament für die Entwicklung der Theorie endlicher Modelle und prägte die Art und Weise, wie Forscher Entscheidungsprobleme und nicht-deterministische Turingmaschinen innerhalb der Komplexitätstheorie angehen.
Akademischer Hintergrund
Fagin wurde 1945 in Oklahoma City geboren, besuchte die Northwest Classen High School und setzte seine Ausbildung am Dartmouth College fort. Er schloss seine Promotion 1973 unter der Betreuung von Robert Vaught an der University of California, Berkeley, ab. Kurz nach seinem Abschluss trat er in die Forschungsabteilung von IBM ein und begann seine Tätigkeit am Thomas J. Watson Research Center.
Beiträge zur Logik und zu Datenbanken
Fagin wechselte 1975 zu IBM Research – Silicon Valley in San Jose, Kalifornien. Seine Arbeit umfasst die Datenbanktheorie und das Schließen über Wissen. Über seinen Satz zur NP-Komplexität hinaus zeigte er, dass die Logik erster Stufe ein Null-Eins-Gesetz besitzt, was bedeutet, dass die Wahrscheinlichkeit, dass eine Formel erster Stufe von einer Struktur mit n Knoten erfüllt wird, gegen null oder eins konvergiert, wenn n gegen unendlich geht. Er entwickelte auch theoretische Rahmenwerke für höhere Normalformen in Datenbanken, insbesondere 4NF, 5NF und DK/NF.
Algorithmen und Anerkennung
Die wissenschaftliche Gemeinschaft verbindet mehrere Konzepte mit seinem Namen, darunter Fagins Algorithmus zur Aggregation von Bewertungen und die Fagin-Inverse, die beim Datenaustausch verwendet wird. Während seiner gesamten Karriere war er Ausschussvorsitzender zahlreicher Fachkonferenzen, wie des ACM Symposium on Principles of Database Systems und der International Conference on Database Theory. Zu seinen Gemeinschaftsarbeiten gehört das Buch Reasoning about Knowledge aus dem Jahr 1995.
Zwanzig Fragen, acht Minuten auf der Uhr und ein Perzentil, gemessen an allen bisherigen Teilnehmern. Ohne Anmeldung.
IQ-Test starten →Ehrungen und Mitgliedschaften
Fagin ist Mitglied der National Academy of Sciences, der National Academy of Engineering, der American Academy of Arts and Sciences und des IEEE. Zu seinen Auszeichnungen gehören der Gödel-Preis 2014, der Alonzo-Church-Preis 2020 und der W. Wallace McDowell Award 2012. Zudem erhielt er die Ehrendoktorwürde der Universität Paris-Dauphine.
Kurzbiografie
- Geboren: 1945, Oklahoma City - Ausbildung: Dartmouth College, University of California, Berkeley - Arbeitgeber: IBM - Wichtigster Satz: Fagins Satz - Ausgewählte Auszeichnung: Gödel-Preis (2014) - Professionelle Mitgliedschaft: ACM Fellow - Bedeutendes Fachgebiet: Theorie endlicher Modelle
Häufig gestellte Fragen
### Was ist Fagins Satz?
Er besagt, dass ein Entscheidungsproblem genau dann in der existenziellen Logik zweiter Stufe ausdrückbar ist, wenn es von einer nicht-deterministischen Turingmaschine in polynomialem Zeitaufwand gelöst werden kann.
### Wo hat Fagin seine Forschung durchgeführt?
Er verbrachte seine Karriere innerhalb der IBM Research Division, hauptsächlich bei IBM Research – Silicon Valley.
