Mulmuleys GCT-Programm

38

Es wird manchmal behauptet, dass Ketan Mulmuleys geometrische Komplexitätstheorie das einzige plausible Programm ist, um die offenen Fragen der Komplexitätstheorie wie die P vs. NP-Frage zu klären. Es gab mehrere positive Kommentare von berühmten Komplexitätstheoretikern zum Programm. Laut Mulmuley wird es lange dauern, bis die gewünschten Ergebnisse erzielt werden. Der Einstieg in das Gebiet ist für allgemeine Komplexitätstheoretiker nicht einfach und erfordert erhebliche Anstrengungen, um die algebraische Geometrie und Darstellungstheorie in den Griff zu bekommen.

  1. Warum wird GCT als in der Lage angesehen, P gegen NP abzurechnen? Was ist der Wert des Anspruchs, wenn es voraussichtlich mehr als 100 Jahre dauert, bis er dort ankommt? Was sind seine Vorteile gegenüber anderen aktuellen Ansätzen und denen, die in den nächsten 100 Jahren aufsteigen könnten?

  2. Wie ist der aktuelle Stand des Programms?

  3. Was ist das nächste Ziel des Programms?

  4. Hat es grundsätzliche Kritik am Programm gegeben?

Ich würde Antworten vorziehen, die für einen allgemeinen Komplexitätstheoretiker verständlich sind, wobei ein Minimum an Hintergrundwissen aus algebraischer Geometrie und Darstellungstheorie vorausgesetzt wird.

cc.complexity-theory big-picture algebraic-complexity p-vs-np gct Anonym
quelle
12
Haben Sie Mulmuleys Tutorial bei FOCS gesehen (verfügbar unter techtalks.tv/talks/1301 ) und haben Sie Ken Regans Exposition gelesen: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley gab definitiv seine Intuition dafür, warum er meint, sein Programm sei realisierbar (und ich denke, er argumentiert, dass es sogar bis zu einem gewissen Grad notwendig ist) und warum es schwierig ist.
Sasho Nikolov
5
Verwandte Blog-Beiträge: 1 , 2 . Auch Scott schreibt: „Mulmuley des GCT - Programm ist der einzige Ansatz für P = NP ich gesehen habe , dass auch ernsthafte Bestrebungen hat‚wissen‘viele nicht - triviale Techniken zur Lösung von Problemen in P (zumindest, Anpassung und lineare Programmierung) Für mich ist das wahrscheinlich das stärkste Argument für GCT. "
Kaveh
7
Ich denke, GCT zielt auf VP vs. VNP und nicht auf P vs. NP.
Iddo Tzameret
6
CVPws¯VNP
4
@Mohammad: Nur weil eine Lösung unerwartet wäre und völlig neue Ideen erfordert, heißt das noch lange nicht, dass die Lösung nicht so funktioniert. In der Tat glauben viele bereits, dass die Lösung von P vs NP mit einer beliebigen Methode völlig neue Ideen erfordert ...
Joshua Grochow

Antworten:

23

Wie von vielen anderen betont, wurde bereits viel zu vielen dieser Fragen von Mulmuley, Regan und anderen gesagt. Ich werde hier nur eine kurze Zusammenfassung der meiner Meinung nach wichtigsten Punkte anbieten, die in den Kommentaren noch nicht erwähnt wurden.

  1. P≠NP

    • Beim Verständnis der algebraischen Varietäten, der Darstellungen und der algorithmischen Fragen, die bei der GCT auftreten, sind einige Fortschritte zu verzeichnen. Die wichtigsten mir bekannten Forscher, die daran gearbeitet haben, sind (in keiner bestimmten Reihenfolge): P. Burgisser, C. Ikenmeyer, M. Christandl, J. M. Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar und natürlich K. Mulmuley und M. Sohoni.

    • n2+232n2+O(n)

    • N. Kayal hat einige Artikel über die algorithmische Frage des Testens, ob sich ein Polynom in der Umlaufbahn eines anderen befindet oder ob es sich um eine Projektion eines anderen handelt. Er zeigt, dass diese Probleme im Allgemeinen NP-schwer sind, aber dass für spezielle Funktionen wie permanente, determinante und elementare symmetrische Polynome diese Probleme in P entscheidbar sind Closure - sind in P für spezielle Funktionen wie Determinante).

  3. Ich habe nicht viel spezifischeres zu sagen als die Antwort auf 2.

  4. Soweit ich weiß, hat es keine grundsätzliche Kritik gegeben, in dem Sinne, dass ich keine Kritik gesehen habe, die das Programm wirklich in irgendeiner Weise diskreditiert. Es gab sicherlich Diskussionen darüber, warum solche Techniken notwendig sein sollten, welchen Wert das Programm angesichts des zu erwartenden langen Zeithorizonts usw. hat, aber ich würde diese eher als gesunde Diskussion als als grundlegende Kritik bezeichnen.

Joshua Grochow
quelle
1
@ user124864: Im Prinzip ja. GCT ist nur ein Ansatz zur Darstellung von Untergrenzen, unabhängig von diesen Untergrenzen. Es scheint, dass es für Funktionen, die durch ihre Symmetrien gekennzeichnet sind, besser funktionieren sollte, aber die letztere Eigenschaft hängt nicht vom numerischen Wert der unteren Grenze ab, die Sie anzeigen möchten (z. B. Quasipoly vs exp).
Joshua Grochow