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 Computertechnologie

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 …

Kennen Sie schon …

Spektrum - Die Woche – Schutz vor Quantenhackern

In dieser Ausgabe von »Spektrum – Die Woche« geht es um einen Wettlauf gegen die Zeit: Programmierer entwickeln Post-Quanten-Algorithmen, um Computer vor den Hackern der Zukunft zu schützen. Ebenso spannend: der Blick zurück in die Geschichte des erfolgreichsten Piraten aller Zeiten: »Black Bart«.

Spektrum - Die Woche – Die Generation »Pandemie«

Wie wirkt sich die Pandemie auf die Hirnentwicklung und das Verhalten von Babys aus? Dieser Frage gehen wir in der aktuellen Ausgabe von »Spektrum – Die Woche« nach. Außerdem erklärt die Kriminologin Britta Bannenberg im Interview, was Betroffenen nach der Amoktat in Heidelberg helfen könnte.

Spektrum der Wissenschaft – Angriff auf den eigenen Körper

»Spektrum der Wissenschaft« berichtet im Artikel »Angriff auf den eigenen Körper«, wie Autoimmunerkrankungen entstehen. Außerdem im Heft: Raumzeitteilchen im Labor, wie Wespen Kakerlaken als Wirt verwenden sowie das Henne-Ei-Problem der Plattentektonik.

Schreiben Sie uns!

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, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften 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 Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften 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