Róbert Szelepcsényi, né le à Žilina en Tchécoslovaquie (aujourd'hui en Slovaquie), est un scientifique slovaque d'origine hongroise.
Biographie Encore étudiant à la Faculté de mathématique, physique et informatique de l'université Comenius de Bratislava, il démontre en 1987, et indépendamment de Neil Immerman, ce qui est connu maintenant sous le nom de théorème d'Immerman-Szelepcsényi. Ce résultat leur a valu l'obtention en 1995 du prix Gödel décerné conjointement par l'ACM et l'EATCS.
Le théorème dit qu'une machine de Turing non déterministe peut résoudre le complémentaire d'un problème en utilisant la même quantité de place que pour le problème initial. Pour la complexité en temps, la même question en est encore ouverte (en 2010), mais on admet généralement qu'un tel énoncé n'existe pas dans ce cas.
En 1993, Róbert Szelepcsényi obtient une maîtrise universitaire ès sciences (M.S.) à l'université de Rochester. Il passe quelque temps en études en vue du Ph.D. à l'université de Chicago. En , il est à l'Académie slovaque des sciences. Un dernier article scientifique de Szelepcsényi paraît en 1999.
Notes et références
Source de la traduction
Liens externes
Catégorie:Naissance en août 1966 Catégorie:Naissance à Žilina Catégorie:Naissance en Tchécoslovaquie Catégorie:Informaticien Catégorie:Mathématicien hongrois Catégorie:Personnalité en informatique théorique Catégorie:Étudiant de l'université Comenius de Bratislava Catégorie:Étudiant de l'université de Rochester Catégorie:Étudiant de l'université de Chicago Catégorie:Lauréat du prix Gödel