Wahrscheinlichkeit der Erzeugung einer gewünschten Permutation durch zufällige Swaps

Ich interessiere mich für das folgende Problem. Wir erhalten als Eingabe eine "Zielpermutation" sowie eine geordnete Liste von Indizes . Beginnend mit der Liste (dh der Identitätspermutation) tauschen wir zu jedem Zeitpunkt das Element in $\sigma\in S_n$ $i_1,\ldots,i_m\in [n-1]$ $L=(1,2,\ldots,n)$ $t\in [m]$ $i_t^{th}$ $L$ mit dem Element, mit unabhängiger Wahrscheinlichkeit . Sei die Wahrscheinlichkeit, dass als Ausgabe erzeugt wird. $(i_t+1)^{st}$ $1/2$ $p$ $\sigma$

Ich würde gerne Folgendes wissen:

Ist die Entscheidung, ob ein vollständiges Problem? $p>0$ $NP$
Ist die Berechnung von genau vollständig? $p$ $\#P$
Was können wir über die Annäherung von an eine multiplikative Konstante sagen ? Gibt es dafür ein PTAS? $p$

Interessant ist auch die Variante, bei der die Swaps nicht aus benachbarten Elementen bestehen müssen.

Beachten Sie, dass es nicht schwer ist, dieses Problem auf kantendisjunkte Pfade (oder auf einen ganzzahligen Multicommodity-Fluss) zu reduzieren. Was ich nicht weiß, ist eine Reduzierung in die andere Richtung.

Update: OK, überprüfen Sie Garey & Johnson, ihr Problem [MS6] ("Permutationsgenerierung") ist wie folgt. Wenn als Eingabe eine Zielpermutation , entscheiden Sie zusammen mit den Teilmengen , ob als Produkt ausgedrückt werden kann , wobei jedes trivial auf alle Indizes wirkt und nicht in . Garey, Johnson, Miller und Papadimitriou (leider hinter einer Paywall) beweisen, dass dieses Problem $\sigma\in S_n$ $S_1,\ldots,S_m\in [n]$ $\sigma$ $\tau_1 \cdots \tau_m$ $\tau_i$ $S_i$ hart. $NP$

$p>0$ $NP$ $S_1,S_2,\ldots$ $S_i$ $S_i$ $\sigma$ $\tau_1 \cdots \tau_m$

$\#P$ $P=NP$

np-hardness counting-complexity permutations sorting-network disjoint-paths Scott Aaronson
quelle

Ich bin mir nicht sicher, ob ich die Frage verstehe. Wo kommt die Wahrscheinlichkeit ins Spiel? Tauschen Sie mit der Wahrscheinlichkeit 1/2 und nicht mit der Wahrscheinlichkeit 1/2?

Arnab

| S_{i} | = 2

$|S_i|=2$

Antworten:

Ich denke, ob p> 0 in Polynomzeit entschieden werden kann.

Das fragliche Problem kann leicht als das Problem der kantendisjunkten Pfade betrachtet werden, wobei der zugrunde liegende Graph ein planarer Graph ist, der aus m + 1 Schichten besteht, von denen jede n Eckpunkte plus m Grad-4-Eckpunkte enthält, um die möglichen benachbarten Swaps darzustellen. Beachten Sie, dass die Planarität dieses Diagramms aus der Tatsache resultiert, dass wir nur benachbarte Swaps zulassen.

Wenn ich mich nicht irre, fällt dies in den Sonderfall des von Okamura und Seymour [OS81] gelösten Problems der kantendisjunkten Pfade. Zusätzlich geben Wagner und Weihe [WW95] einen linearen Zeitalgorithmus für diesen Fall an.

Siehe auch Goemans 'Vorlesungsunterlagen [Goe12], die eine schöne Darstellung des Okamura-Seymour-Theorems und des Wagner-Weihe-Algorithmus geben.

Verweise

[Goe12] Michel X. Goemans. Vorlesungsunterlagen, 18.438 Advanced Combinatorial Optimization, Vorlesung 23 . Massachusetts Institute of Technology, Frühjahr 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura und Paul D. Seymour. Multicommodity-Flüsse in planaren Graphen. Journal of Combinatorial Theory, Reihe B , 31 (1): 75–81, August 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner und Karsten Weihe. Ein linearer Zeitalgorithmus für kantendisjunkte Pfade in planaren Graphen. Combinatorica , 15 (1): 135–150, März 1995. http://dx.doi.org/10.1007/BF01294465

Tsuyoshi Ito
quelle