OpenAI-Algorithmus löst SAT nur jenseits von 10^10.000.000.000.000.000.000.000.000 Variablen
Efficient algorithms, the Exponential Time Hypothesis, and losing the plot
Der argmin-Autor seziert die jüngste OpenAI-Ankündigung eines subexponentiellen Algorithmus für das Erfüllbarkeitsproblem. Der Haken: Bis zu einer unvorstellbaren Variablenzahl von 10^10.000.000.000.000.000.000.000.000 führt der Algorithmus schlicht eine erschöpfende Suche aus – also genau das, was Jack Edmonds 1965 als „schlecht“ verwarf. Die eigentliche Erkenntnis: Der jahrzehntelange Fokus auf Polynomialzeit als Definition von Effizienz hat die Komplexitätstheorie von der realen Computation entfremdet.
Ich bin kein Wettmensch, aber ich habe eine Vorhersage: Es wird sich herausstellen, dass P=NP in einem galaktischen Sinne gilt, und alles, was wir lernen werden, ist, dass wir fünfzig Jahre damit verbracht haben, die falsche Frage zu beantworten.