kompletność rozpoznania różnicy dwóch permutacji

Shor stwierdził w swoim komentarzu do odpowiedzi anonimowego łosia na to pytanie. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? , To jest -Complete do określenia różnicę dwóch permutacji. Niestety, nie widzę prostą redukcję od problemu sumy permutacji i warto mieć zmniejszenie -completeness dla problemu różnicy permutacji. $NP$ $NP$

Różnica permutacji:

INSTANCJA: Tablica dodatnich liczb całkowitych. $A[1...n]$

Pytanie: Czy istnieją dwie permutacje i dodatnich liczb takie, że dla ? $\pi$ $\sigma$ $1,2, ... , n$ $|\pi(i) - \sigma(i)| = A[i]$ $1 \le i \le n$

Co jest zmniejszenie do udowodnienia -completeness rozpoznawania różnicy dwóch permutacji? $NP$

EDIT 09.10.2014 : Komentarz shor za daje redukcję co dowodzi -completeness gdy elementy sekwencji są podpisane różnice. Jednak nie widzę łatwej redukcji mojego problemu, w którym wszystkie elementy są bezwzględnymi wartościami różnic. $NP$ $A$ $A$

UPDATE: Problem Różnica wydaje się być permutacji -Complete nawet jeśli jeden z dwóch permutacji jest zawsze permutacji tożsamość. Dowód twardości tego specjalnego przypadku jest bardzo pożądany. Tak więc jestem zainteresowany kompletnością tej ograniczonej wersji: $NP$ $NP$

Ograniczona permutacja Różnica: INSTANCJA: Tablica dodatnich liczb całkowitych. $A[1...n]$

~~PYTANIE: Czy istnieje taki permutacji dodatnich liczb takie, że dla ? $\pi$ $1,2, ... , n$ $|\pi(i) - i| = A[i]$ $1 \le i \le n$~~

Aktualizacja 2 : Ograniczony problem można skutecznie rozstrzygnąć, jak pokazuje odpowiedź mjqxxxx. Złożoność obliczeniowa pierwotnego problemu nie została udowodniona.

EDYCJA 9/6/16 : Jestem zainteresowany ustaleniem, czy to uproszczenie Różnicy Permutacyjnej jest NP-pełne:

Różnica w ograniczonej permutacji:

INSTANCJA : Multiset dodatnich liczb całkowitych. $A$

PYTANIE : Czy istnieje taki permutacji dodatnich liczb takie, że ? $\pi$ $1,2, ... , n$ $A= \{|\pi(i) - i| :1 \le i \le n\}$

— Mohammad Al-Turkistany
źródło

Dlaczego nie zapytać bezpośrednio Piotra? @Peter

— caozhu

Czy masz na myśli przez e-mail? Zrobię to.

— Mohammad Al-Turkistany

Być może czegoś mi brakuje, ale czy nie można przedstawić tego problemu jako 2-SAT, a tym samym rozwiązać go w polityce czasowej? Możemy założyć WLOG, że jedną z permutacji jest tożsamość (zakładam tutaj, że A [i] jest obliczana cyklicznie; czy to ma duże znaczenie?), A następnie możemy przedstawić drugą macierz

. Bycie macierzą permutacji jest koniunkcją zdań dwóch zmiennych stwierdzających, że żadne dwa nie leżą w rzędzie ani w kolumnie; a następnie stwierdzenie, że różnica w lokalizacjach pi (i) od i to A [i] to OR z dwóch możliwych miejsc, w których może się ona znajdować.

x [i, j]

$x[i,j]$

— Noam

@Noam Dziękujemy za komentarz. Ciekawy pomysł. Nie myślałem o tym. Jednak nie jest dla mnie oczywiste, czy doprowadzi to do algorytmu wielomianowego czasu, tym bardziej, że otrzymujemy tylko bezwzględną wartość różnic.

— Mohammad Al-Turkistany

Tak, wydaje się, że różnica między liczeniem luki cyklicznie lub w wartości bezwzględnej może mieć znaczenie.

— Noam

Odpowiedzi:

Ograniczony problemem, gdzie jednym z permutacji jest tożsamość, to z pewnością w . Zbuduj dwuczęściowy wykres, w którym każdy wierzchołek jest połączony z elementem (ami) tak, aby . Następnie żądana permutacja $\mathsf{P}$ $i \in V_1=\{1,2,\ldots,n\}$ $j \in V_2=\{1,2,\ldots,n\}$ $|i-j|=A[i]$ $\sigma$ istnieje wtedy i tylko wtedy, gdy wykres ma idealne dopasowanie (tj. dopasowanie z krawędziami), które można określić w czasie wielomianowym. $n$

— mjqxxxx
źródło

Być może czegoś mi brakuje, ale idealne dopasowanie nie będzie działać. Musisz udowodnić istnienie ograniczonego idealnego dopasowania. Rozważmy całkowitą

występujący dwukrotnie w wejściowym tablicy

. Idealne dopasowanie, które odpowiada permutacji, musi mieć dwie krawędzie z absolutną różnicą

. Twój algorytm NIE dowodzi istnienia takiego ograniczonego dopasowywania. To właśnie sprawia, że problem jest trudny i prawdopodobnie NP-kompletny.

k

$k$

A

$A$

k

$k$

— Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Myślę, że jeśli

są powiązane z węzłami

A [i] = A [j] = k

$A[i] = A[j] = k$

u_{i}, u_{j} \in V_{1}

$u_i, u_j \in V_1$

v_{i + A [i]}, v_{i - A [i]}, v_{j + A [j]}, v_{j - A [j]} \in V_{2}

$v_{i+A[i]},v_{i-A[i]},v_{j+A[j]},v_{j-A[j]} \in V_2$ z różnicami bezwzględnymi

. Idealne dopasowanie będzie obejmować co najmniej jedną krawędź

jedną krawędź

. Doszedłem do tego samego wniosku kilka razy temu, myśląc o pierwotnym problemie, ale w inny sposób: zobaczyłem, że łatwo jest sformułować ograniczony problem jako formułę 2-SAT (jeśli chcesz, mogę dodać odpowiedź z nim , ale pomysł mjqxxxx jest lepszy).

k

$k$

u_{i}

$u_i$

u_{j}

$u_j$

— Marzio De Biasi,

@MarzioDeBiasi Dlaczego to podejście (i twoje) nie działa w przypadku pierwotnego (nieograniczonego) problemu?

— Mohammad Al-Turkistany,

@mjqxxx Widzę, że twoje podejście rozwiązuje ograniczony przypadek. Dlaczego nie można go rozszerzyć, aby skutecznie rozwiązać pierwotny problem?

— Mohammad Al-Turkistany,

@ MohammadAl-Turkistany: ponieważ w pierwotnym problemie elementy pierwszej permutacji (

jest w wersji ograniczonej) nie są naprawione, a stosując to samo podejście otrzymujesz wykres trójstronny (i w moim podejściu 2-SAT z a

klauzula ... która nie jest klauzulą 2-CNF).

i

$i$

δ_{i} (n) \to (π_{i} (n + A [i]) \lor π_{i} (n - A [i]))

$\delta_i(n) \to (\pi_i(n+A[i]) \lor \pi_i(n-A[i]))$

— Marzio De Biasi,

Oto dość interesująca odmiana, w której problem jest łatwy: zamiast zestawu podstawowego , zezwól na dowolny podzbiór . Nadal celem jest znalezienie permutacji , aby gdzie $\{1,2,3,\ldots,n\}$ $\{1,2,4,8,\ldots\}$ $\pi$ $A = \{|\pi(2^k) - 2^k| : 2^k \in \Omega\}$ $\Omega$ jest podstawą. Główną zaletą jest to, że nowy zestaw gruntu zmusza każdy element do dla niektórych , a jeśli , to i są przez to określone różnica. Wynika z tego, że dla każdej różnicy w możemy wywnioskować, że $A$ $2^{k_1}-2^{k_2}$ $k_1,k_2$ $k_1\ne k_2$ $k_1$ $k_2$ $|2^{k_1} - 2^{k_2}|$ $A$ lub (lub oba). $\pi(2^{k_1}) = 2^{k_2}$ $\pi(2^{k_2}) = 2^{k_1}$

Skuteczne rozwiązanie tej uproszczonej odmiany jest więc mniej więcej rutynowe. Rozpocznij od skonstruowania dwukierunkowej multigrafii gdzie i są wyraźnymi kopiami zestawu podłoża i dodaj krawędzie i kiedykolwiek pojawia się w $G = (L \sqcup R, E)$ $L$ $R$ $(2^{k_1},2^{k_2})$ $(2^{k_2},2^{k_1})$ $|2^{k_1} - 2^{k_2}|$ z . Twierdzę, że następujące są równoważne: $A$ $k_1 \ne k_2$

Istnieje permutacja z różnicami $\pi$ $A$
Każdy wierzchołek w ma stopień 0 lub 2 $G$

Tak naprawdę nie udowodnię tego z powodu czasu, ale nie jest tak źle, aby samemu to wypracować. Że jest proste. To $1 \implies 2$ $2 \implies 1$ $G$ $L$ $R$ $G$ $G$ $\pi$ $L$ $R$

Możesz sformułować powyższy algorytm jako idealnie pasujące pytanie i wyobrażam sobie, że istnieją inne redukcje do 2-SAT. Nie wiem jednak, jak rozszerzyć te podejścia na pierwotny problem.

— Andrew Morgan
źródło