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 – Higher denn je

Crack auf dem Vormarsch: Wir zeigen, wie sich Deutschlands Drogenproblem 2025 darstellt – mit Zahlen, Analysen und politischen Fragen. Außerdem: Warum Camping nicht immer klimafreundlich ist, was ein Mathe-Streit mit der ABC-Vermutung zu tun hat und mehr.

Spektrum der Wissenschaft – Quantengravitation im Labor: Experimente könnten die Quantennatur der Raumzeit enthüllen

Zwei Artikel in dieser Ausgabe stellen neue Experimente und Versuchsideen vor, die das postulierte Quantenteilchen der Schwerkraft, das Graviton, sowie die die Quantennatur der Raumzeit nachweisen sollen. Aktuell werden die ersten Versuche dieser Art umgesetzt und von der Fachwelt mit Spannung verfolgt. Daneben berichten wir über Tensornetzwerke, die klassische Computer leistungsfähiger machen als gedacht und so eine Konkurrenz für Quantencomputer darstellen. Außerdem: wie gentechnisch maßgeschneiderte Phagen – Viren, die Bakterien befallen – in der Medizin eine wichtige Rolle übernehmen könnten, neue Erkenntnisse über die neolithische Revolution am Amazonas und die Diskussion, ob auch in der Ökologie eine Replikationskrise besteht.

Spektrum - Die Woche – Wenn das Stromnetz aus dem Takt gerät

Mit Solarmodulen, Hochspannungsleitungen und Batterien sind wir vertraut. Phasenschieber, Stromrichter und Schwungmasse könnten bald ebenso wichtig sein. Nach dem Blackout in Spanien und Portugal analysiert unser Autor die Ursachen und Lösungen für die Stabilität des europäischen Stromsystems.

  • 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

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!

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.