Millennium-Probleme

• Im Jahr 2000 erstellter Liste ungelöster Probleme der Mathematik
• Für die Lösung eines dieser Probleme wird ein Preisgeld gewährt.
• Millennium-Probleme
  • Beweis der Poincaré-Vermutung in der Topologie (solved)
  • Beweis der Vermutung von Birch und Swinnerton-Dyer aus der Zahlentheorie
  • Beweis der Vermutung von Hodge aus der algebraischen Geometrie
  • Analyse von Existenz und Regularität von Lösungen des Anfangswertproblems der dreidimensionalen inkompressiblen Navier-Stokes-Gleichungen.
  • Lösung des P-NP-Problems der Informatik
  • Beweis der Riemannschen Vermutung der Zahlentheorie
  • Erforschung der Gleichungen von Yang-Mills

P vs NP Problem

• Problem der Komplexitätstheorie in der theoretischen Informatik¹².

• P – Menge aller Probleme:

  • „schnell“ lösbar sind

• NP – Menge aller Probleme:

  • gefundene Lösung kann „schnell“ überprüft werden
  • Lösungsfindung allerdings „langsam“

• „schnell“ lösbar bzw. eine Lösung als „schnell“ prüfbar (siehe [comparison])

  • Anstieg des Rechenaufwands wird durch mit (Polynomfunktion) beschränkt
  • „langsam“: Anstieg durch (Exponentialfunktion) beschränkt

    

• Menge P wird als Teilmenge von NP gesehen

  

• Viele NP Probleme im Laufe der Zeit zu P Problemen geworden -> effizientere Algorithmen / Lösungsstrategien gefunden

• Sind alle NP Probleme = P Probleme und wir müssen nur weiter suchen?

P vs NP Problem

• Viele reale Probleme in NP (traveling salesman, bin packing, …)
• Ein Beweis könnte fundamentale Auswirkungen haben
  • Manche glauben aber auch sehr geringe Auswirkungen da keine „direkten“ Auswirkungen

Beispiel: Sudoku

Sudokus sind NP-Harte Probleme, “einfach” zu verifizieren, aber “langsam” lösbar mit steigender Problemgröße.

Beispielsweise, in aufsteigender Komplexität³:

• 2x2 Sudoku

  

• 3x3 Sudoku

  

• 4x4 Sudoku