Róbert Szelepcsényi (* 19. August 1966 in ŽilinaGeburtsdaten nach Milan Strhan, David Daniel (Herausgeber), Slovakia and the Slovaks: A concise encyclopedia, Encyclopedic Institute of the Slovak Academy of Sciences, 1994) 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 1987Róbert Szelepcsényi The Method of Forced Enumeration for Nondeterministic Automata, Acta Informatica, Band 26, 1988, S. 279–284 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 ChicagoEhemalige Wissenschaftler in der Abteilung theoretische Informatik Universität Chicago und war Ende der 1990er Jahre an der Slowakischen Akademie der Wissenschaften.
Einzelnachweise
Kategorie:Informatiker Kategorie:Person (Comenius-Universität Bratislava) Kategorie:Tschechoslowake Kategorie:Slowake Kategorie:Geboren 1966 Kategorie:Mann