OpenAI widerlegt eine jahrzehntealte Annahme der Informatik
A.I. Just Blew Up a Key Tenet of Computer Science

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.
- fsmv
Alte Kamellen, und der ETH-Beweis hat buchstäblich keinerlei Auswirkungen auf P vs. NP oder irgendetwas anderes auch nur entfernt Praktisches
- peri-cl
Außerdem
https://news.ycombinator.com/item?id=50251661 („The Exponential Time Hypothesis Is False [pdf] (github.com/openai)“, 309 Kommentare)
- matt3210
IPO-Köder