Róbert Szelepcsényi

Róbert Szelepcsényi (* 19. August 1966 in Žilina[1]) 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[2] 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[3] und war Ende der 1990er Jahre an der Slowakischen Akademie der Wissenschaften.[4]

Einzelnachweise

1. Geburtsdaten nach Milan Strhan, David Daniel (Herausgeber), Slovakia and the Slovaks: A concise encyclopedia, Encyclopedic Institute of the Slovak Academy of Sciences, 1994
2. Róbert Szelepcsényi The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica, Band 26, 1988, S. 279–284
3. Ehemalige Wissenschaftler in der Abteilung theoretische Informatik Universität Chicago
4. University of Rochester, Department of Computer Science (Memento des Originals vom 4. Januar 2013 im Internet Archive)  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