Kann man einen Nachbarn eines Scheitelpunkts in der Grafik eines Polytops effizient und gleichmäßig abtasten?

Ich habe ein Polytop $P$ das durch $\{ x : Ax \leq b, x \geq 0\}$ .

Frage: Gibt es einen Polynom-Zeit-Algorithmus, um bei gegebenem Scheitelpunkt $v$ von $P$ gleichmäßig von den Nachbarn von $v$ im Graphen von $P$ ? (Polynom in der Dimension, die Anzahl der Gleichungen und die Darstellung von $b$ . Ich kann davon ausgehen, dass die Anzahl der Gleichungen in der Dimension polynom ist.)

Update: Ich denke, ich konnte zeigen, dass dies NP-schwer ist, siehe meine Antwort, die das Argument erklärt. (Und mit $NP$ -hard meine ich, dass ein polynomieller Zeitalgorithmus beweisen würde, dass $RP = NP$ ... nicht sicher ist, welche Terminologie hier richtig ist.)

Update 2: Es gibt eine 2 line Nachweis von $NP$ -Härte (angesichts der richtigen kombi Polytop) und ich konnte es einen Artikel von Khachiyan finden. Siehe Antwort für Beschreibung und Link. :-D

Ein gleichwertiges Problem :

In den Kommentaren wies Peter Shor darauf hin, dass diese Frage gleichbedeutend ist mit der Frage, ob wir gleichmäßig von den Eckpunkten eines gegebenen Polytops abtasten können. (Ich denke, die Äquivalenz sieht folgendermaßen aus: In einer Richtung können wir von einem Polytop $P$ mit einem Scheitelpunkt $v$ zu der Scheitelpunktzahl bei $v$ , $P/v$ , und das Abtasten der Scheitelpunkte von $P/v$ entspricht dem Abtasten der Nachbarn von $v$ auf $P$ In der anderen Richtung können wir von einem Polytop $P$ zu einem Polytop $Q$ einer höheren Dimension übergehen, indem wir einen Kegel mit der Spitze $v$ und der Basis hinzufügen $P$ . Dann ist das Abtasten der Nachbarn von $v$ in $Q$ gleichbedeutend mit dem Abtasten der Eckpunkte von $P$ )

Diese Formulierung der Frage wurde zuvor gestellt: /mathpro/319930/sampling-uniformly-from-the-vertices-of-a-polytope

reference-request np-hardness counting-complexity linear-programming polytope Lorenzo Najt
quelle

Ich kenne die Antwort auf Ihre Frage nicht, aber meines Wissens gibt es keine bekannte NP-Härte, um einen Scheitelpunkt eines explizit angegebenen Polytops gleichmäßig abzutasten. Beispielsweise sind ungefähr Abtastzyklen NP-hart. Wenn es jedoch ein lineares Programm gäbe, dessen Scheitelpunkte Zyklen codieren, könnten Sie sehr wahrscheinlich die Länge des Zyklus optimieren und so den Hamilton-Zyklus lösen.

Heng Guo

Eine andere Bemerkung ist, dass selbst wenn Ihre Frage eine positive Antwort hat, sie keinen einheitlichen Sampler für die Eckpunkte liefert (unter der Annahme der 0-1-Polytop-Vermutung). Das Skelett des Polytops ist in den meisten interessanten Fällen nicht regelmäßig, und die Grade können exponentiell variieren.

Heng Guo

@ HengGuo Nochmals vielen Dank für die Kommentare, sie sind sehr hilfreich. Kennen Sie zufällig ein gutes Beispiel, bei dem die Grade exponentiell variieren? (Ich bin nicht überrascht, dass dies für allgemeine Polytope passieren kann. Es wäre schön, ein kombinatorisches Beispiel zu haben, wenn Sie eines auf den Kopf stellen

könnten

Betrachten Sie das unabhängige Mengenpolytop eines zweigliedrigen Graphen. Zwei Eckpunkte (zwei unabhängige Mengen) werden verbunden, wenn ihre symmetrische Differenz einen verbundenen Untergraphen induziert. Nehmen Sie nun einen zweigliedrigen Graphen, dessen eine Seite nur zwei Eckpunkte hat,

verbindet sich mit jedem Eckpunkt auf der anderen Seite und

nur mit einem. Betrachten Sie unabhängige Mengen

und

v_{1}

$v_1$

v_{2}

$v_2$

{v_{1}}

$\{v_1\}$

{v_{2}}

$\{v_2\}$

Heng Guo

Das gleichmäßige Abtasten der benachbarten Scheitelpunkte eines gegebenen Scheitelpunkts eines Polytops ist das gleiche Problem wie das gleichmäßige Abtasten eines zufälligen Scheitelpunkts eines Polytops. Schneiden Sie einen Kegel in der Nähe des Scheitelpunkts infinitesimal ab. Man hat dann ein neues Polytop, und wenn Sie einen Scheitelpunkt dieses neuen Polytops abtasten können, können Sie einen benachbarten Scheitelpunkt des ursprünglichen Polytops abtasten. Ich würde vermuten, dass dies ungefähr in BPP ist, aber ich kann kein Papier finden, das dies beweist.

Peter Shor

Antworten:

Edit 2: Peinlicherweise gibt es einen zweizeiligen Beweis für die $NP$ -Härte, wenn man mit dem richtigen Polytop beginnt.

Denken Sie zunächst an das Zirkulationspolytop eines Diagramms am Ende von Seite 4 von Die Generierung aller Eckpunkte eines Polyeders ist schwierig .

Ihre Scheitelpunkte stimmen bijektiv mit den gerichteten einfachen Zyklen überein. Daher sind sie nach JVV Proposition 5.1 nur schwer zu erfassen oder zu zählen . :-D

Ausgestattet mit diesen Schlüsselwörtern konnte ich die Härte des Stichprobenergebnisses als Satz 1 von Transversalen Hypergraphen und Familien polyedrischer Kegel von Khachiyan finden.

Edit: Ich habe das folgende Argument aufgeschrieben, und es scheint korrekt zu sein. Es gibt jedoch ein viel einfacheres Argument, das ich hier skizzieren werde:

a) Durch Analyse von Backtrack-Algorithmen zur Auflistung aller Eckpunkte und aller Flächen eines konvexen Polyeders (Fukuda et al.) ist es stark schwierig, das folgende Problem auf Polytopen zu lösen:

Eingabe: Ein Polytop $Ax = b , x \geq 0$ in $\mathbb{R}^n$ eine Teilmenge $S \subseteq n$

Ausgabe: Gibt an, ob es einen Scheitelpunkt $v$ von $P$ , der für jede der Koordinaten in $S$ ungleich Null ist .

b) Vor diesem Hintergrund kann man die folgende Konstruktion : neue Variablen $y_{ik}$ für $i \in S$ und $k = 1, \ldots, d$ einführen und die Ungleichung $0 \leq y_{ik} \leq x_i$ einführen . Rufen Sie das resultierende Polytop $P_{S,d}$ . Der Zweck dieser Konstruktion besteht darin, über jedem Scheitelpunkt einen Hyperwürfel der Dimension $d |supp(x) \cap S|$ einzuführen .

c) Man kann überprüfen, dass die Eckpunkte dieses Polytops alle über den Eckpunkten des alten Polytops liegen und dass die Anzahl der Eckpunkte über einem Eckpunkt $2^{d | supp(x) \cap S|}$ beträgt , wobei $supp$ die Funktion ist, die einen Scheitelpunkt zu den Koordinaten sendet, bei denen er ungleich Null ist.

d) durch eine übliche Kette von bigons Typ Argumente folgt, daß , indem man $d$ ausreichend groß ist , eine gleichförmige Probe , die von den Scheitelpunkten $P_{S,d}$ würde (mit hohen Wahrscheinlichkeit) einer Probe aus dem Scheitel gibt die Größe ihrer Kreuzung mit der maximiert $S$ .

Es scheint verschiedene Erweiterungen zu geben. Ich werde mit einem Link aktualisieren, wenn das Schreiben abgeschlossen ist.

(Das alte Argument war früher hier - es befindet sich im Bearbeitungsverlauf. Ich habe es entfernt, weil es sehr lang ist und die Suche nach der richtigen Antwort auf die Frage behindert.)

Lorenzo Najt
quelle

Das ist ein sehr interessantes Argument! Ich habe nicht alle Details in Teil 3 vollständig überprüft (was sind die Funktionen

?), Aber im Prinzip kann jede nicht übergreifende Struktur nur eine überexponentielle Explosion verursachen, die Somit kann gesteuert werden, indem ein

Polynom groß genommen wird.

H_{1}

$H_1$

H_{0}

$H_0$

l e a v e s

$leaves$

d

$d$

Heng Guo

@ HengGuo Danke fürs Lesen! Von

Ich meine die Anzahl der Komponenten und

die Dimension des Zyklusraums (Schaltungsrang) und "verlässt" die Anzahl der Vertices vom Grad 1. Ich werde diese Definitionen hinzufügen.

| H_{0} |

$|H_0|$

| H_{1} |

$|H_1|$

Lorenzo Najt

Daran muss etwas falsch sein. Wenn es ein Polytop gibt, dessen Eckpunkte Lassos und einfache Zyklen sind, können wir dann nicht mit linearer Programmierung eine beliebige lineare Funktion für dieses Polytop maximieren? Und würden wir dann in der Polynomzeit nicht ein übergreifendes Lasso finden?

Peter Shor

@PeterShor Ich denke, das passiert nicht, weil das Polytop in der Hyperebene lebt, die durch Setzen der Summe der Kantenvariablen auf eins definiert wird. Diese Funktion ist also über das Polytop konstant. Die Funktion, die die Anzahl der Kanten darstellt, ist die Größe des Trägers des Vektors, der auf diesem Polytop nicht linear ist.

Lorenzo Najt

@PeterShor Ich habe einen Beweis hinzugefügt, dass die Funktion 'Anzahl der Kanten' nicht linear sein kann, siehe das Bild unten.

Lorenzo Najt