Unsicherheiten im GCT-Programm

8

In https://en.wikipedia.org/wiki/Geometric_complexity_theory wird erwähnt, dass ".. Ketan Mulmuley glaubt, dass das Programm, wenn es realisierbar ist, wahrscheinlich etwa 100 Jahre dauern wird, bis es das P vs. NP-Problem lösen kann".

Es scheint darauf hinzudeuten, dass das einzige derzeit realisierbare Programm auf ernsthafte Hindernisse stoßen könnte.

Was sind einige der Hindernisse, bei denen das Programm scheitern könnte?

T ....
quelle
Ich bin mir nicht sicher, was Sie unter "dem einzigen derzeit realisierbaren Programm" verstehen. Sie meinen innerhalb der GC oder aller Ansätze für P vs NP? Übrigens ist die Auflösung von P gegen NP nicht das einzige Maß für die Nützlichkeit dieser oder anderer Theorien ... Alle Angriffe auf P gegen NP waren bisher mit ernsthaften Hindernissen konfrontiert ...
vzn
1
Ich denke nicht, dass dieses Programm "nur derzeit tragfähiges Programm" ist. Es gibt mehrere praktikable Programme und Ansätze, und GCT ist eines davon. In den letzten Jahren haben wir in vielen dieser Programme schöne Fortschritte erzielt. Ryan Williams 'Beweis für ACC, der nicht in NEXP enthalten ist, und die Methode der verschobenen partiellen Ableitungen sind zwei Beispiele, die mir in den Sinn kommen ...
Oder Meir

Antworten:

11

Es hängt davon ab, was Sie als "GCT-Programm" zählen.

  1. Betrachten Sie den spezifischen Vorschlag ( GCT I , GCT II ), das Verschwinden / Nicht-Verschwinden bestimmter Multiplizitäten in den Umlaufbahnverschlüssen der Determinante und der permanenten zu verwenden, um die Vermutung der starken permanenten gegenüber der Determinante aufzulösen (dh, dass sich die permanente nicht in der Umlaufbahn befindet) jede polynomiell größere Determinante). In diesem Fall ist es möglich, dass sich dies, selbst wenn die Vermutung zutrifft, nicht im Verschwinden / Nicht-Verschwinden einer Vielzahl von Irreps widerspiegelt, die auf diesen Umlaufbahnverschlüssen unterstützt werden. Es ist sogar möglich, dass sich die Vermutung nicht in der entsprechenden Ungleichheit der Multiplizitäten widerspiegelt. Ich sollte beachten, dass es verschiedene Formen von Beweisen gibt, dass dies nicht passieren sollte, aber es wurde noch nicht offiziell ausgeschlossen.

Beachten Sie jedoch, dass , wenn anstelle von Mannigfaltigkeiten Sie lediglich einen wollen Trennmodul , dann ist die starke zul v det Vermutung ist wahr , wenn und nur wenn ein Trennmodul vorhanden ist .

  1. Wenn Ihr Ziel ist die ursprüngliche permanent gegen Determinante Vermutung gibt es einen früheren Schritt in GCT, nämlich (Wie von chazisop) auf die starke zul v det Vermutung zu bewegen , indem sie die Umlaufbahn unter Berücksichtigung Verschlüsse . Es ist denkbar, dass die ursprüngliche permanente versus determinante Vermutung wahr ist, aber die starke Version falsch ist. Dies erscheint mir jedoch höchst unwahrscheinlich. Wenn dies der Fall ist, kann keine unserer derzeitigen Methoden die Perm-Det-Vermutung annähernd lösen, da sie derzeit alle für die Version "stark" / "approximativ" / "Grenze -" / Zariski-geschlossen funktionieren von welcher algebraischen Komplexitätsaussage sie auch beweisen.

  2. NPP/poly

  3. [Mögliche Ausfälle von Untergrenzen im Allgemeinen, nicht spezifisch für GCT.] GCT zielt derzeit auf ungleichmäßige Untergrenzen ab; Das heißt, selbst beim GCT-Ansatz für boolesche Untergrenzen soll . Aber natürlich stimmt es mit den aktuellen Theoremen dass noch . Natürlich ist es auch technisch möglich, dass und die perm v det-Vermutung falsch ist!NPP/polyPNPNPP/polyP=NP

Lassen Sie mich jedoch darauf hinweisen, dass das derzeitige GCT-Programm für mich immer noch das erste ist, was ich versuchen sollte . Wenn sich herausstellt, dass einer der obigen (1) - (3) tatsächlich nicht funktioniert, bedeutet dies, dass die Vermutung von perm v det (und damit versus ) fast unvorstellbar ist schwieriger als wir derzeit denken. (Es kann erwähnenswert sein, dass diese Aussage von jemandem stammt, der bereits der Meinung ist, dass die folgende Analogie ungefähr richtig, wenn nicht unzureichend ist: unserem derzeitigen Kenntnisstand als Die Klassifikation endlicher einfacher Gruppen erfolgt nach Fermats kleinem Satz . Und selbst wenn das der Fall ist,PNPPNPDas Verständnis der genauen Art und Weise, in der der Fehler auftritt, ist wahrscheinlich wichtig, um weitere Fortschritte zu erzielen .

Joshua Grochow
quelle
2
Es wird schön sein, wenn die Notizen auf veröffentlicht werden. Viele weitere Forscher könnten Kommentare abgeben, da dies die Version ist, die am häufigsten untersucht wird (ohne algebraische Dauerwelle gegenüber Det-Version). 3.NPP/poly
T ....
Könnten Sie in zu "..Ich sollte beachten, dass es verschiedene Arten von Beweisen gibt" einen Kommentar abgeben ? 1.
T ....
5

Ich glaube, die Aussage "100 Jahre" bezieht sich darauf, dass die Theorie allgemein ist, aber tiefes Verständnis und neue Ergebnisse in der Darstellungstheorie und der algebraischen Geometrie erfordert, um voranzukommen, was möglicherweise nur langsam voranschreitet (ich möchte einen Vergleich mit der Zahlentheorie anstellen, aber Ich bin mir nicht sicher, wie passend es ist.

Außerdem gibt es einen Präzisionsverlust bei der Übersetzung in die algebrogeometrische Welt: Anstatt eine Untergrenze für die Eigenschaften einer Komplexitätsklasse zu beweisen (dh Polynome, die verschwinden, wenn Objekte in dieser Klasse als Eingabe angegeben werden), beweisen Sie dies gegen seinen Zariski-Verschluss (der oben genannten Polynome). Es ist denkbar, dass man, um die beiden zu trennen, die Grenze dieses Verschlusses untersuchen muss (jene Polynome, die nur im Verschluss, aber auf der ursprünglichen Menge auftreten). Es wird angenommen, dass dies in der determinanten vs. permanenten Variante des GCT-Programms wahrscheinlich der Fall ist .

Aus persönlicher Erfahrung heraus unterscheidet sich das Know-how, das erforderlich ist, um GCT gründlich zu verstehen, erheblich von dem, was normalerweise in Bachelor- oder sogar Masterstudiengängen in CS im Mittelpunkt steht. Im Wesentlichen ist es eine natürliche Folge der Entscheidung, GCT zu studieren, um die Voraussetzungen zu erlernen.

Chazisop
quelle
Nein, es scheint einige Hindernisse zu geben, die das Programm zunichte machen könnten. Es ist ein möglicher Weg, der nicht unbedingt auf den richtigen Zutaten 'ab sofort' basiert
T ....
Ich würde sagen, der zweite hat das Potenzial, ein solches Hindernis zu sein, aber es ist sehr schwierig, diese Frage genau zu beantworten. Stellen Sie sich zum Beispiel vor, Sie stellen dieselbe Frage für dieselbe Frage für das P vs NP-Problem im Allgemeinen, bevor die Barrieren der Relativierung, der natürlichen Beweise und der Algebrisierung bekannt waren. Ich nehme an, ich habe die beiden anderen Teile aufgenommen, weil mir die Aussage "100 Jahre" immer etwas willkürlich erschien. Joshua Grochow ist sowohl in der GCT sehr gut informiert als auch verwendet die Theorie. Es würde mich sehr interessieren, eine Antwort von ihm zu sehen.
Chazisop