Róbert Szelepcsényi

Róbert Szelepcsényi (* 19. August 1966 in Žilina<ref>Geburtsdaten nach Milan Strhan, David Daniel (Herausgeber), Slovakia and the Slovaks: A concise encyclopedia, Encyclopedic Institute of the Slovak Academy of Sciences, 1994</ref>) ist ein slowakischer Informatiker ungarischer Abstammung.

Leben und Werk

Szelepcsenyi, der Sohn des Musikers Jan Szelepcsenyi (* 1937), bewies als Student an der Comenius-Universität in Bratislava 1987<ref>Róbert Szelepcsényi The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica, Band 26, 1988, S. 279–284</ref> unabhängig von Neil Immerman den Satz von Immerman und Szelepcsényi in der Komplexitätstheorie, wofür beide 1995 den Gödel-Preis erhielten. Der Satz besagt, wenn eine Entscheidungsproblem durch eine nicht-deterministische Maschine mit logarithmisch beschränktem Speicherraum gelöst werden kann, auch das komplementäre Problem (mit vertauschten ja/nein Antworten) von einer solchen Maschine gelöst werden kann. Für die zeitliche Komplexität ist das Problem ungelöst (2018) und es wird allgemein vermutet, dass ein entsprechender solcher Satz in diesem Fall nicht gilt.

1993 erhielt er einen Masterabschluss an der University of Rochester, war an der Universität Chicago<ref>Ehemalige Wissenschaftler in der Abteilung theoretische Informatik Universität Chicago</ref> und war Ende der 1990er Jahre an der Slowakischen Akademie der Wissenschaften.<ref>University of Rochester, Department of Computer Science (Memento des Vorlage:IconExternal vom 4. Januar 2013 im Internet Archive) Datei:Pictogram voting info.svg Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.cs.rochester.edu</ref>

Einzelnachweise

<references />