Róbert Szelepcsényi

Róbert Szelepcsényi (* 19. August 1966 in Zilina^[1]) ist ein slowakischer Informatiker ungarischer Abstammung.

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, dass ein nicht-deterministischer Automat zu einem Problem auch das komplementäre Problem lösen kann bei asymptotischen gleichem zur Verfügung stehendem Speicherraum. Für die zeitliche Komplexität ist das Problem ungelöst (2010) und es wird allgemein vermutet, dass ein entsprechender solcher Satz in diesem Fall nicht gilt.

1993 erhielt er einen Master Abschluss 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, Encyclopedial 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