imported>Schotterebene: Änderungen von 2003:E6:174C:BF34:C8B9:FF22:F2FE:8F8B (Diskussion) auf die letzte Version von Aka zurückgesetzt

2022-09-29T09:27:08Z

Änderungen von 2003:E6:174C:BF34:C8B9:FF22:F2FE:8F8B (Diskussion) auf die letzte Version von Aka zurückgesetzt

Neue Seite

'''Lance Jeremy Fortnow''' (* [[1963]]) ist ein amerikanischer [[Informatiker]].

Fortnow studierte Mathematik und Informatik an der [[Cornell University]] (Bachelor 1985) und wurde 1989 bei [[Michael Sipser]] am [[Massachusetts Institute of Technology]] promoviert (''Complexity theoretic aspects of interactive proof systems''). 1989 wurde er Assistant Professor, 1994 Associate Professor und 2003 Professor für Informatik an der [[University of Chicago]]. Seit 2008 ist er Professor an der [[Northwestern University]] und Adjunct Professor am Toyota Technology Institute at Chicago und außerdem seit 2008 am Kellogg Graduate Institute of Management Science. 1996/97 war er als [[Fulbright-Programm|Fulbright]]-Stipendiat Gastprofessor am [[Centrum Wiskunde & Informatica]] in [[Amsterdam]] und 1999 bis 2003 Senior Scientist am NEC Research Institute in [[Princeton (New Jersey)|Princeton]]. 2001/2002 war er Gastprofessor an der [[Princeton University]].

Zu seinen Doktoranden zählt [[Carsten Lund]], und mit diesem und [[László Babai]] erzielte er Anfang der 1990er Jahre wichtige Fortschritte in der Komplexitätstheorie von zufallsgesteuerten Beweissystemen (Probabilistic Checkable Proofs, PCP) bzw. [[Interaktives Beweissystem|interaktiven Beweissystemen]]. Insbesondere bewiesen sie, dass die Klasse der Beweise von [[Nichtdeterministische Turingmaschine|nicht-deterministischen Turingmaschinen]] mit exponentiellem Zeitaufwand in der Klasse PCP (mit polynomialer Komplexität der Fragen und der verwendeten Zufallszahlen) ist ('''[[NEXPTIME|NEXP]]''' ⊆ '''PCP'''[poly(''n''), poly(''n'')]). Die Bemühungen, die Klasse zu erweitern führten dann in den 1990er Jahren zum [[PCP-Theorem]].

Seit den 2000er Jahren beschäftigt er sich auch mit Anwendungen der Komplexitätstheorie in den Wirtschaftswissenschaften, wo er unter anderem das [[Gefangenendilemma]] mit Duke Whang spieltheoretisch untersuchte und logarithmische Prognoseregeln für Märkte (Market Scoring Rules) von [[Robin Hanson]].

Seit 2007 ist er Fellow der [[Association for Computing Machinery]]. Er ist Mitgründer und Herausgeber der ACM Transactions on Computation Theory.

== Schriften ==
* ''The Golden Ticket: P, NP, and the Search for the Impossible'', Princeton University Press 2013, ISBN 0691156492.
* [http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext Fortnow: ''Status of P vs. NP'', Comm. ACM Bd. 52, 2009, S. 78–86], Übersichtsartikel zum Status des [[P-NP-Problem]]s
* Mit Steve Homer: [http://people.cs.uchicago.edu/~fortnow/papers/history.pdf ''A short history of computational complexity'', Bulletin of the European Association for Theoretical Computer Science, Band 80, Juni 2003, PDF-Datei]
* Mit [[Carsten Lund]], Howard Karloff und Noam Nisan: ''Algebraic methods for interactive proof systems'', Journal of the ACM, Band 39, 1992, S. 859–868
* Mit [[László Babai]] und Carsten Lund: ''Non deterministic exponential time has two prover interactive protocols'', Computational Complexity, Band 1, 1991, S. 3–40

== Weblinks ==
* [http://lance.fortnow.com/ Website] (englisch)
* [http://blog.computationalcomplexity.org/ Blog von Fortnow über Komplexitätstheorie] (englisch)

{{Normdaten|TYP=p|GND=1034850725|LCCN=n/2012/78791|VIAF=293401328}}

{{SORTIERUNG:Fortnow, Lance}}
[[Kategorie:Informatiker]]
[[Kategorie:Mitglied der Association for Computing Machinery]]
[[Kategorie:Hochschullehrer (Northwestern University)]]
[[Kategorie:Hochschullehrer (University of Chicago)]]
[[Kategorie:US-Amerikaner]]
[[Kategorie:Geboren 1963]]
[[Kategorie:Mann]]

{{Personendaten
|NAME=Fortnow, Lance
|ALTERNATIVNAMEN=Fortnow, Lance Jeremy (vollständiger Name)
|KURZBESCHREIBUNG=amerikanischer Informatiker
|GEBURTSDATUM=1963
|GEBURTSORT=
|STERBEDATUM=
|STERBEORT=
}}

Lance Fortnow - Versionsgeschichte

imported>Schotterebene: Änderungen von 2003:E6:174C:BF34:C8B9:FF22:F2FE:8F8B (Diskussion) auf die letzte Version von Aka zurückgesetzt