Op vrijdag 7 september 2007 bezoeken drie van 's werelds meest toonaangevende theoretische informatici het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Die middag organiseert het CWI ter ere van zijn onderzoeker Paul Vitányi de CWI Lectures in Mathematics and Computer Science. Sprekers zijn Ming Li (University of Waterloo), Andrew Yao (Beijing University) en Leonid Levin (Boston University).
Kolmogorov complexiteit
Paul Vitányi is een van 's werelds belangrijkste onderzoekers op het gebied van Kolmogorov complexiteit, de theorie die de complexiteit van een object meet aan de hand van de kortste beschrijving van het object. Dit idee uit de theoretische informatica geeft een fundamentele kijk op willekeurigheid. Het heeft geleid tot nieuwe inzichten en toepassingen in onder andere de statistiek, informatietheorie en zelfs de grondslagen van de wiskunde. De theorie kan gebruikt worden om een objectieve afstandsmaat tussen allerlei soorten bestanden uit verschillende onderzoeksgebieden te definiëren. Zo heeft de methode bijvoorbeeld geheel automatisch ontdekt dat het SARS-virus een variant is van het Corona-virus. Maar ook zou de computer kunnen herkennen of een toneelstuk echt door Shakespeare geschreven is. Vitányi heeft op het CWI de quantum computing groep opgericht. Hij is CWI Fellow en hoogleraar aan de Universiteit van Amsterdam.
Toptrio
Het werk van het toptrio Li, Yao en Levin is sterk verwant met dat van Vitányi. Li is samen met Vitányi auteur van het standaardwerk An Introduction to Kolmogorov Complexity and its Applications, waarvan delen zijn vertaald in het Russisch, Japans en Chinees. Yao schreef in 2000 de Turing Award op zijn naam, de meest prestigieuze prijs in de informatica. Hij heeft fundamentele bijdragen geleverd aan het genereren van pseudo-random getallen en cryptografie. Levin is mede-ontdekker van 'NP-compleetheid', wellicht het belangrijkste idee in de theoretische informatica. Veel praktische relevante optimaliseringsproblemen zoals het handelsreizigerprobleem lijken exponentieel veel rekentijd te kosten; hoe snel onze computers ook ooit nog zullen worden. De vraag of er niet toch een slim computerprogramma bestaat dat deze berekeningen veel sneller kan doen staat bekend als het P vs. NP probleem, volgens het Clay Mathematics Institute een van de zeven 'Millennium Math Problems'.
