Wydajny algorytm dla istnienia permutacji z sekwencją różnic?

To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji.

Sekwencja różnic permutacji liczb jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi liczbami w permutacji . Innymi słowy, dla $a_1, a_2, \ldots a_n$ $\pi$ $1, 2, \ldots n+1$ $\pi$ $a_i= |\pi(i+1)-\pi(i)|$ $1 \le i \le n$

Na przykład sekwencja jest sekwencją różnic w permutacji . Podczas gdy sekwencje i nie są sekwencją różnic jakiejkolwiek permutacji liczb . $1, 1, 3$ $2 3 4 1$ $2, 2, 3$ $3, 1, 2$ $1, 2, 3, 4$

Czy istnieje skuteczny algorytm określający, czy dana sekwencja jest sekwencją różnic dla pewnej permutacji , czy też jest NP-trudna? $\pi$

EDYCJA : Otrzymujemy problem równoważny obliczeniowo, jeśli sformułujemy problem za pomocą permutacji kołowych.

EDIT2 : Wpisany na łamach MathOverflow, Jak trudne jest rekonstruowanie permutacji z jej sekwencji różnic?

EDIT3 Przyznano nagrodę za szkic dowodu i przyjąłbym odpowiedź po otrzymaniu pełnego dowodu formalnego.

EDIT 4 : Marzio miłe dowód -completeness został opublikowany w Electronic Journal kombinatoryki . $NP$

cc.complexity-theory co.combinatorics np-hardness permutations Mohammad Al-Turkistany
źródło

Być może innym trywialnym (ale bardziej dźwiękowym?) Komentarzem jest to, że jeśli

są permutacją

(wszystkie wartości są różne), problemem jest sprawdzenie, czy sekwencja jest wdzięcznym oznaczeniem linii

węzły, które można rozwiązać w czasie wielomianowym.

a_{i}

$a_i$

[1.. n]

$[1..n]$

n + 1

$n+1$

Marzio De Biasi,

@MarzioDeBiasi Myślisz, że podzielasz moją pasję do problemów związanych z permutacją. Mam nadzieję, że wpadłem na najprostszy pod względem obliczeniowym problem permutacji :)

Mohammad Al-Turkistany,

:-) ... Wolę powiedzieć, że mój komentarz pochodzi bezpośrednio z godzin, które na próżno spędziłem na wdzięcznym problemie z etykietowaniem drzew ... Mam jednak niejasne pojęcie o możliwej całkowitej redukcji NP dla twojego problemu; jeśli uda mi się go sformalizować, opublikuję odpowiedź.

Marzio De Biasi,

@MarzioDeBiasi Znalazłem ten interesujący komentarz Shora, stwierdzający, że twój problem, planowanie pracy z problemem wąskiego gardła , jest równoważny specjalnemu przypadkowi mojego problemu. Oto komentarz Shora: jeśli

, problem jest równoznaczny ze znalezieniem permutacji

więc

K = 2 N

$K=2N$

1...2 N

$1...2N$

i_{2 a - 1} - i_{2 a} = A_{i}

$i_{2a−1}−i_{2a}=A_i$ . To kolejny dowód na kompletność

mojego problemu.

N P

$NP$

Mohammad Al-Turkistany

Odpowiedzi:

To jest szkic możliwej redukcji, aby udowodnić, że jest trudny do NP:

$a_i$ $...11111...$

$2$ $1112112111$

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

Otwory należy wypełnić w pozostałej części permutacji.

3) używając wystarczająco dużego 1SEQ, następnie 1SEQ z pewnymi dziurami, a następnie kolejnego dużego 1SEQ możesz zbudować linię wymuszoną ;

4) łącząc wiele linii wymuszonych, możesz zbudować wykres siatki permutacji, w którym węzły odpowiadają brakującym liczbom w leżącej u podstaw permutacji wymuszonej.

Na przykład sekwencja 1111111112111111111112111111111 wymusza następujący wykres siatki permutacji 5x7:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14   
 1  2  3  4  5  6  7

$w \times w$ $a,b$ $|a-b|=kw$

$G$

$G$ $G$

7) możesz wypełnić wszystkie otwory (tj. Zakończyć permutację) wtedy i tylko wtedy, gdy oryginalny wykres siatki ma cykl hamiltonowski

EDYCJA: 27 lipca 2013 r

Próbowałem formalnie udowodnić kompletność problemu NP: wprowadziłem nowy problem (problem Crazy Frog ), którym jest NPC. Problem rekonstrukcji permutacji z różnic jest równoważny z „Problemem szalonej żaby 1-D bez zablokowanych komórek” (który jest również NPC).

Aby uzyskać szczegółowe informacje na temat redukcji, zobacz moje pytanie / odpowiedź na temat „Dwie warianty ścieżki hamiltonowskiej” lub pobierz projekt dowodu „Kiedy żaba spełnia permutację” :)) (wciąż sprawdzam / wypełniam ją)

Marzio De Biasi
źródło

Fajnie, jestem pewien, że doprowadzi to do rozwiązania, gadżet wyboru jest zdecydowanie możliwy do zrealizowania.

domotorp

@domotorp: Zamieściłem (opublikuję szczegóły części do wyboru / synchronizacji w najbliższych dniach); może zawiera błąd, którego nie widzę, jednak stawiam 1 $ , że całą redukcję można znacznie uprościć :-)

Marzio De Biasi

@MarzioDeBiasi Ładna wizualizacja. Wygląda na to, że jesteś na dobrej drodze. Czy możesz podać swoją odpowiedź na MathOverflow, ponieważ problem jest bardzo zainteresowany?

Mohammad Al-Turkistany

@MarzioDeBiasi Czy możesz zamieścić swoją ostateczną odpowiedź (formalną) przed wygaśnięciem nagrody?

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Właśnie wróciłem z podróży, postaram się sformalizować (i sprawdzić w CSP) gadżety w najbliższych dniach.

Marzio De Biasi,