Nachauswahl in der geometrischen Komplexitätstheorie

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.

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. $perm$$det$$V_{perm}$$V_{det}$$V_{perm} \subseteq V_{det}$$perm$$p$$det$

2. $V_{perm} \not\subseteq V_{det}$

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 $perm$$p$$det$$perm$

[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 $P$$det$$perm$$p$$det$

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=NP\cap co-NP$

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