Sam Buss
Samuel R. „Sam“ Buss (* 6. August 1957) ist ein US-amerikanischer Informatiker und mathematischer Logiker.
Buss studierte an der Emory University mit dem Bachelor-Abschluss 1979 und an der Princeton University, an der er 1983 seinen Master-Abschluss erhielt und 1985 bei Simon Kochen promoviert wurde (Bounded arithmetic).[1] Ab 1986 war er Lecturer an der University of California, Berkeley. Ab 1988 war er Assistant Professor und ab 1993 Professor an der University of California, San Diego.
Buss befasst sich mit mathematischer Logik, Beweiskomplexität und Komplexitätstheorie.
Er gilt als einer der Väter beschränkter Arithmetik (bounded arithmetic), das heißt abgeschwächten Versionen der Peano-Arithmetik, in der zum Beispiel die Quantoren beschränkt sind. Sie wurde 1971 von Rohit Jivanlal Parikh eingeführt. Buss befasste sich damit 1985 im Rahmen seiner Dissertation, die auch als Buch veröffentlicht wurde und ein Standardwerk auf diesem Gebiet ist.
1987 bewies er, dass das Boolesche Evaluierungsproblem ALOGTIME (alternating log time) ist.[2]
Für 2019 erhielt er den Gödel-Preis.
Schriften (Auswahl)
- Bounded Arithmetic, Neapel: Bibliopolis, 1986, Online
Weblinks
Einzelnachweise
- Sam Buss im Mathematics Genealogy Project (englisch)
- Buss, The Boolean formula value problem is in ALOGTIME, in: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), 1987, S. 123–131. Online auf seiner Homepage