Direkt zum Inhalt
Login erforderlich
Dieser Artikel ist Abonnenten mit Zugriffsrechten für diese Ausgabe frei zugänglich.

Informatik: Wie komplex darf es sein?

Kann ein Computer die Lösung eines Problems immer in vertretbarer Zeit überprüfen, egal wie schwierig es ist? Ja, sagt ein neuer Beweis - und widerlegt damit eine ganze Reihe etablierter Vermutungen aus der Mathematik und Physik.
Künstlerische Darstellung der ComputertechnologieLaden...

Wissenschaftler lieben es, Dinge zu kategorisieren – zumindest auf abstrakter Ebene. Chemiker teilen beispielsweise alle Elemente in das Periodensystem ein, Biologen ordnen Lebewesen nach Familien und Arten, und Mathematiker haben im vergangenen Jahrzehnt, nach langer Suche, alle endlichen einfachen Gruppen gefunden und aufgelistet.

Informatiker suchen ebenfalls nach Ordnung, wenn auch ein wenig anders: Sie sortieren Probleme nach ihrer Komplexität. Bereits in der Vergangenheit haben sie herausgefunden, dass gewisse Aufgaben für Computer sehr einfach zu lösen sind. Bei ihnen wächst mit der Länge des Problems die zur Lösung nötige Rechenzeit bloß langsam (polynomial) an. Aus Sicht von Informatikern gehören sie damit zur so genannten Komplexitätsklasse P.

Probleme, die schwer zu lösen sind, sich aber einfach überprüfen lassen, zählen hingegen zur Klasse NP. Ein Beispiel ist ein anspruchsvolles Sudoku-Rätsel: Bei diesem ist es schwierig, die passenden Zahlen zu finden. Hat man sie jedoch einmal ausgetüftelt oder bekommt ein ausgefülltes Blatt präsentiert, lässt sich leicht überprüfen, ob es korrekt ist. Ob P und NP wirklich verschiedene Klassen sind oder ob man einfach noch keinen Algorithmus kennt, der die entsprechenden Probleme effizient löst, zählt zu den wichtigsten offenen Fragen der theoretischen Informatik. Sie ist eines der sieben Millennium-Probleme, deren Lösung das Clay Mathematics Institute mit je einer Million US-Dollar belohnt.

Mit P und NP fängt der Spaß aber erst an. Computerwissenschaftler haben mittlerweile eine Hierarchie von Komplexitätsklassen herausgearbeitet, von sehr einfachen hin zu extrem anspruchsvollen Aufgaben …

Juli 2020

Dieser Artikel ist enthalten in Spektrum der Wissenschaft Juli 2020

Kennen Sie schon …

Unendlich

Spektrum Kompakt – Unendlich

Seit Jahrtausenden fasziniert uns das Konzept der Unendlichkeit. Und noch immer steckt es voller Rätsel und Überraschungen.

27/2020

Spektrum - Die Woche – 27/2020

Der Atomkern

Spektrum Kompakt – Der Atomkern

Protonen, Neutronen, Quarks, Gluonen - allein die Bausteine zu kennen, reicht nicht. Denn viele rätselhafte Phänomene zeigen, dass Atomkerne mehr sind als die Summe ihrer Komponenten.

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Ito, T., Vidick, T.: A multi-prover interactive proof for NEXP sound against entangled provers. ArXiv 1207.0550, 2012

Ji, Z. et al.: MIP* = RE. ArXiv 2001.04383, 2020

Natarajan, A., Wright, J.: NEEXP in MIP*. ArXiv 1904.05870, 2019