Nachauswahl in der geometrischen Komplexitätstheorie

8

Kontext: Soweit ich weiß, dient in der Theorie der geometrischen Komplexität das Vorhandensein von Hindernissen sozusagen als Nachweis für das Nichtvorhandensein einer effizienten Rechenschaltung für die explizite harte Funktion im betrachteten Problem der unteren Grenze. Nun gibt es einige andere Annahmen für Hindernisse, dass sie kurz, leicht zu überprüfen und leicht zu konstruieren sein müssen.

Frage: Meine Frage lautet: Ich habe ein Problem, von dem ich vermute, dass es in Polynomzeit lösbar ist. Wie kann ich dann zeigen, dass es für dieses Problem keine Hindernisse gibt, dh wenn keine Hindernisse vorhanden sind, kann das Problem effizient berechnet werden und es befindet sich tatsächlich in Polynomzeit.

Ansatz: Ich denke, und ich kann mich in dieser Behauptung irren, dass das Zeigen, dass keine Hindernisse vorhanden sind, einer Standardreduktion von NP-Problemen auf andere Probleme gleichkommen kann, deren Komplexität noch unbekannt ist, in dem Beweis, dass sie selbst in NP sind. In diesem Fall kann man also nach Möglichkeit zeigen, dass Hindernisse vorhanden sind, wenn versucht wird, ein NP-Problem auf das betrachtete Problem zu reduzieren. Auf diese Weise ist die Reduzierung unlösbar. Welche Rolle spielt dabei auch die Nachauswahl? Ist es möglich, das Nichtvorhandensein von Hindernissen einfach nachzuwählen? Vielen Dank und entschuldigen Sie das Fehlen präziser Aussagen in meinem Ansatz und meinen Fragen.

Betrachten Sie als weiteres Beispiel ein Problem X , von dem wir wissen, dass es in P ist. Nehmen wir nun an, wir wussten nicht, dass dieses Problem in Polynomzeit lösbar ist. Dann ist es möglich, dass man die folgende Behauptung aufstellen kann:

Da bei der Berechnung von X keine Hindernisse vorhanden sind, können wir sagen, dass es sich um die Klasse P handelt

Von da an besteht das Problem darin, dass die einfache (rechnerische) Entdeckung dieser Hindernisse, falls überhaupt eine vorhanden ist, zeigen würde, dass X nicht in Polynomzeit ist. Es ist jedoch eine schwierige Aufgabe, den anderen Weg zu gehen, dh festzustellen, dass keine Hindernisse vorhanden sind.

dhillonv10
quelle
Ich möchte auch hinzufügen, dass ich mir nicht vorstellen kann, wie die unlösbare Reduzierung dazu führen würde, dass das Problem frei von Hindernissen ist. Wie kann man diese Idee erweitern?
Dhillonv10

Antworten:

5

Es kommt darauf an, was Sie unter "existiert kein Hindernis" verstehen. Wenn Sie "Behinderung" im allgemeinen Sinne einer Art Nachweis dafür meinen, dass das Problem nicht in , dann habe ich keine Ahnung, wie ich Ihre Frage beantworten soll, da der Begriff "Behinderung" noch vage ist. Wenn Sie "Behinderung" speziell im darstellungstheoretischen Sinne von Mulmuley-Sohoni meinen, dann ist hier die Antwort:P

Für die Zwecke dieser Antwort können wir das Mulmuley-Sohoni GCT-Programm in zwei Schritte unterteilen:

  1. permdetVpermVdetVpermVdetpermpdet

  2. VpermVdet

Es ist zu beachten, dass die Implikation in (2) nur in eine Richtung geht (das Vorhandensein von Hindernissen impliziert keine Einbeziehung von Sorten), so dass es möglich ist, dass keine Projektion von und dennoch keine repräsentationstheoretischen Hindernisse existieren. In diesem Fall reicht es also nicht aus, nur zu beweisen, dass keine Hindernisse vorhanden sind, um zu zeigen, dass einfach ist. Andererseits ist in (1) die Einbeziehung algebraischer Varietäten sowohl notwendig als auch ausreichend für die Einbeziehung von Komplexitätsklassen.p d e t p e r mpermpdetperm

[Oben wurden natürlich viele Details weggelassen - die Abhängigkeit von der Eingabegröße, wie man über die Komplexitätsklasse anstelle von spricht , die Tatsache, dass die Einbeziehung von Sorten äquivalent zu ist, die durch Projektionen von angenähert werden kann , ... Aber die Essenz stimmt immer noch.]d e t p e r m p d e tPdetpermpdet

Joshua Grochow
quelle
Ich verstehe, danke für diese Antwort, Josh. Grundsätzlich stellt sich also heraus, dass, wenn man ein gegebenes Problem auf eine darstellungstheoretische Form reduzieren kann, wie im GCT-Programm gezeigt, man durch die Methode der Hindernisse zeigt, dass diese Klassen trennbar sind. Im Allgemeinen scheint es mir unentscheidbar zu sein, zu zeigen, dass keine Hindernisse einfach sind.
Dhillonv10
Obwohl ich die Antwort geschlossen habe, weil die Hauptfrage, die ich hatte, Hindernisse betraf, würde ich mich freuen, wenn Sie (@ joshua-grochow) kommentieren könnten, wie die Nachauswahl eine Rolle spielen könnte. Vielen Dank.
Dhillonv10
@ dhillonv10 Es fiel mir schwer, genau zu verstehen, was Sie über die Nachauswahl fragten, aber vielleicht liegt es nur daran, dass ich noch nicht viel über die Nachauswahl weiß. Es tut uns leid.
Joshua Grochow
np, nochmals vielen Dank.
Dhillonv10
5

Ich denke auch gerne so und verbinde es mit der Vermutung. Es wird dort oder dort erwähnt ( es fällt mir schwer, Seiten über diese Vermutung zu finden, da ich nur mit mathematischen Symbolen darauf verweisen kann, die Google nicht mag).P=NPcoNP

Ein Problem liegt in NP vor, wenn Sie ein Zertifikat für eine "wahre" Antwort geben können (Beispiel: ein Hamilton-Zyklus für das TSP-Problem oder eine gültige Zuweisung für das SAT-Problem). In Co-NP können Sie ein Zertifikat für eine "falsche" Antwort geben (Beispiel: ein "Beweis", dass die SAT-Formel nicht erfüllt werden kann, ein schlechter Schnitt in einem Diagramm, das die Existenz eines Hamilton-Zyklus verhindert usw.). ..)

Tatsächlich können dies die "Hindernisse" sein, auf die Sie sich möglicherweise auch beziehen. Und bei dieser Vermutung geht es darum zu sagen: Ein Problem, das in NP liegt, ist polynomisch, wenn ich weiß, was die Hindernisse sind.

Jetzt können die "Hindernisse" viele verschiedene Formen annehmen. Für das Übereinstimmungsproblem (das ein Polynom ist) kann es eine Partition des Graphen sein (siehe Tuttes Charakterisierung von Graphen, die eine perfekte Übereinstimmung zulassen ), oder es kann das von Farkas 'Lemma für die lineare Programmierung ausgestellte Zertifikat sein (und Graphenprobleme, die reduziert werden können) dazu). Es kann tatsächlich sehr viele Dinge sein, und so "benutze" ich diese Vermutung normalerweise in eine Richtung: Wenn ich keine Hindernisse finde, schließe ich nicht, dass mein Problem NP-schwer ist. Einige Hindernisse sind wirklich schwer zu finden ... Aber wenn ich einen komplizierten Polynomalgorithmus für ein Problem habe, bin ich manchmal davon überzeugt, dass "es eine verständliche Menge von Hindernissen geben muss, die leichter zu verstehen sind als der komplizierte Algorithmus".

Naja ... meine zwei Cent :-)

Nathann

Nathann Cohen
quelle
Vielen Dank für die Erkenntnisse, Nathan. Das Hauptproblem hier ist das, was Sie erwähnen. Es gibt keine Möglichkeit, absolut sicher zu sein, dass ein Problem keine Hindernisse aufweist. Mulmuley bezeichnet dies als P-Barriere, bei der das Auffinden einiger Hindernisse exponentielle Zeit in Anspruch nehmen kann.
Dhillonv10