CWI-onderzoekers ontwikkelen nieuwe berekeningsmethode

Publication date: 19-06-2014


Katalytisch geheugen is de nieuwe term voor een berekeningsmethode die  geheugen gebruikt  "zonder het te gebruiken". Dat wil zeggen, de computer doet een berekening waarbij hij geheugen gebruikt  dat al helemaal vol zit, en laat dat geheugen na gebruik weer in de staat achter waarin het voor de berekening werd  aangetroffen.

Dat dit überhaupt kan is zeer tegenintuïtief en werd voor onmogelijk gehouden. In een  artikel van CWI-onderzoekers Harry Buhrman, Bruno Loff en Florian Speelman in samenwerking met  Richard Cleve (University of Waterloo, Canada) en Michal, Koucký (Charles University Praag), wordt aangetoond dat dat niet alleen mogelijk is maar aanleiding geeft tot een nieuwe complexiteitsklasse en een nieuwe manier om over geheugengebruik na te denken met toepassingen binnen de cryptografie.

Een uitgebreide review van het artikel wordt gegeven in het veelgelezen weblog van Richard Lipton over theoretisch informatica. Het artikel is deze maand gepresenteerd op de prestigieuze ACM Symposium on the Theory of Computing (STOC).

Bron: UvA/CWI