Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany

Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m ∈ [ n - 1 ] L = ( 1 , 2 , ... , n ) t ∈ [ m ] I T H T L ( i t + 1 ) e t 1 / 2 s $\sigma\in S_n$$i_1,\ldots,i_m\in [n-1]$$L=(1,2,\ldots,n)$$t\in [m]$$i_t^{th}$$L$$(i_t+1)^{st}$$1/2$$p$$\sigma$

Chciałbym wiedzieć (dowolny z):

• Czy decydowanie, czy jest problemem zupełnym?N $p>0$$NP$
• Czy obliczanie dokładnie ?# $p$$\#P$
• Co możemy powiedzieć o przybliżeniu do stałej multiplikatywnej? Czy istnieje na to PTAS?$p$

Interesujący jest również wariant, w którym zamiany nie muszą zawierać sąsiadujących elementów.

Zauważ, że nie jest trudno zredukować ten problem do ścieżek rozłącznych na krawędziach (lub do przepływu o wartościach całkowitych o wartości całkowitej); to czego nie wiem to redukcja w innym kierunku.

Aktualizacja: OK, sprawdzanie Garey & Johnson, ich problem [MS6] („Generowanie permutacji”) jest następujący. Podane jako dane wejściowe permutacja docelowa , wraz z podzbiorami , decydują, czy jest wyrażalny jako produkt , gdzie każdy działa trywialnie na wszystkie indeksy nie są w . Garey, Johnson, Miller i Papadimitriou (za ścianą płatną, niestety) udowadniają, że ten problem jest twardy.S 1 , … , S m ∈ [ n ] σ τ 1 ⋯ τ m τ i S i N $\sigma\in S_n$$S_1,\ldots,S_m\in [n]$$\sigma$$\tau_1 \cdots \tau_m$$\tau_i$$S_i$$NP$

Jeśli swapy nie muszą sąsiadować, to sądzę, że oznacza to, że decydując, czy jest również N P- twardym. Redukcja jest po prostu taka: dla każdego S 1 , S 2 , … w kolejności zaoferujemy zestaw „zamian kandydatów”, który odpowiada kompletnej sieci sortowania na S i (tj. Zdolnej do arbitralnej permutacji S i , podczas gdy działając trywialnie na wszystko inne). Wtedy σ będzie wyrażane jako τ 1 ⋯ τ m , jeśli i tylko jeśli jest osiągalne jako iloczyn tych zamian.$p>0$$NP$$S_1,S_2,\ldots$$S_i$$S_i$$\sigma$$\tau_1 \cdots \tau_m$

To wciąż pozostawia otwartą „oryginalną” wersję (w której zamiana dotyczy tylko sąsiednich elementów). Dla wersji liczenia (z dowolnych swaps), to oczywiście silnie sugeruje, że problem powinien być -Complete. W każdym razie, to wyklucza a PTA chyba że P = N P .$\#P$$P=NP$

Myślę, że o tym, czy p> 0 można ustalić w czasie wielomianowym.

Problem, o którym mowa, można łatwo rzucić jako problem z rozłącznymi krawędziami, gdzie leżący pod spodem wykres jest płaskim planem składającym się z m +1 warstw, z których każda zawiera n wierzchołków plus m stopni-4 wierzchołków reprezentujących możliwe sąsiednie zamiany. Zauważ, że płaskość tego wykresu wynika z faktu, że dopuszczamy tylko sąsiednie zamiany.

Jeśli się nie mylę, dotyczy to szczególnego przypadku problemu ścieżek rozłącznych krawędzi rozwiązanych przez Okamurę i Seymour [OS81]. Ponadto Wagner i Weihe [WW95] podają dla tego przypadku algorytm czasu liniowego.

Zobacz także uwagi do wykładu Goemansa [Goe12], które dają ładne przedstawienie twierdzenia Okamura – Seymour i algorytmu Wagnera – Weihe.

Bibliografia

[Goe12] Michel X. Goemans. Notatki z wykładu, 18.438 Zaawansowana optymalizacja kombinatoryczna, Wykład 23 . Massachusetts Institute of Technology, wiosna 2012. http://math.mit.edu/~goemans/18438S12/lec23.pdf

[OS81] Haruko Okamura i Paul D. Seymour. Przepływy wielokomorowe na wykresach płaskich. Journal of Combinatorial Theory, Series B , 31 (1): 75–81, August 1981. http://dx.doi.org/10.1016/S0095-8956(81)80012-3

[WW95] Dorothea Wagner i Karsten Weihe. Algorytm czasu liniowego dla ścieżek rozłącznych krawędzi na wykresach płaskich. Combinatorica , 15 (1): 135-150, 1995. marzec http://dx.doi.org/10.1007/BF01294465