OpenAI widerlegt eine jahrzehntealte Annahme der Informatik

A.I. Just Blew Up a Key Tenet of Computer Science

OpenAI widerlegt eine jahrzehntealte Annahme der Informatik

Eine seit 1998 geltende Vermutung besagte, dass bestimmte Rechenprobleme für Computer immer unlösbar schnell bleiben würden – ähnlich wie Sudoku zu lösen weit schwerer ist, als eine Lösung zu prüfen. Am 26. Oktober meldete OpenAI, seine neueste KI-Technologie habe die Exponential Time Hypothesis (E.T.H.) widerlegt. Das eigentliche P-vs.-NP-Problem bleibt offen, doch die Widerlegung weckt Hoffnungen auf radikal effizientere Algorithmen.

Wenn P und NP der Intuition folgen, dann sollten sie auf keinen Fall gleich sein.
  1. fsmv

    Alte Kamellen, und der ETH-Beweis hat buchstäblich keinerlei Auswirkungen auf P vs. NP oder irgendetwas anderes auch nur entfernt Praktisches

  2. peri-cl

    Außerdem

    https://news.ycombinator.com/item?id=50251661 („The Exponential Time Hypothesis Is False [pdf] (github.com/openai)“, 309 Kommentare)

  3. matt3210

    IPO-Köder

Mehr von diesem Tag

2026-11-17