Wie das Online-Portal Spektrum berichtet, gab das Team um den Forscher Zhengfeng Ji in einem Fachaufsatz die Antwort, wie Computer selbst solche Probleme lösen können, die extrem anspruchsvollen Komplexitätsklassen zugeordnet werden – und zwar in vertretbarer Berechnungszeit.
Wie Spektrum ausführt, stellten Informatiker, um Probleme klassifizieren zu können, interaktive Beweissysteme auf. Die Annahme: Theoretisch könnten Computer mit unendlicher Speicherkapazität im Prinzip komplizierte Probleme berechnen. Diese als „Beweisführer“ bezeichneten Computer seien allerdings nicht vertrauenswürdig. Es bedürfe zusätzlich eines „Prüfers“, der das Ergebnis nachrechnet. Dieser Prüfer sei im Rahmen des Beweissystems allerdings ein Computer mit begrenzten Ressourcen, dessen nötige Berechnungsdauer nur langsam mit der Länge des Problems ansteigen darf. Eine der höchsten Komplexitätsklassen wird in diesem System mit „MIP*“ bezeichnet, die Entscheidungsprobleme umfasst, deren Antwort Ja oder Nein lautet und die ein Computer in endlicher Zeit bestimmen kann. Darunter fällt laut Spektrum das sogenannte „Halteproblem“. Das heißt: Es wird bestimmt, ob ein Computer bei der Berechnung einer Aufgabe zu einer Lösung und damit zum Halten kommt oder unendlich weiterrechnet.
Größte Überraschung aus der Informatik in diesem Jahrhundert
Das Team der technischen Universität Sydney sagt nun, ein Prüfer könne in vertretbarer Zeit das Ergebnis eines anderen Computers bewerten, das besagt, dass eine bestimmte Aufgabe in einer gewissen Zeit lösbar ist und nicht unendlich berechnet wird. Der renommierte Wissenschaftler Scott Aaronson von der University of Austin schrieb, sollte die Arbeit einer unabhängigen Prüfung standhalten, handle es sich um eine der größten Überraschungen aus der theoretischen Informatik in diesem Jahrhundert.
Laut Spektrum wirkt sich das Ergebnis auch auf die Mathematik und Quantenphysik aus und würde die vom Fields-Medaillen-Preisträger Connes aufgestellte „Einbettungsvermutung“ widerlegen.
deutschlandfunk
Tags:
