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

12

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 1 , 2 , n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi liczbami w permutacji π . Innymi słowy, a i = | π ( i + 1 ) - π ( i ) | dla 1 i na1,a2,anπ1,2,n+1πai=|π(i+1)π(i)|1in

Na przykład sekwencja jest sekwencją różnic w permutacji 2 3 4 1 . Podczas gdy sekwencje 2 , 2 , 3 i 3 , 1 , 2 nie są sekwencją różnic jakiejkolwiek permutacji liczb 1 , 2 , 3 , 4 .1,1,323412,2,33,1,21,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?π

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

Mohammad Al-Turkistany
źródło
1
Być może innym trywialnym (ale bardziej dźwiękowym?) Komentarzem jest to, że jeśli są permutacją [ 1 .. n ] (wszystkie wartości są różne), problemem jest sprawdzenie, czy sekwencja jest wdzięcznym oznaczeniem linii n + 1 węzły, które można rozwiązać w czasie wielomianowym. ai[1..n]n+1
Marzio De Biasi,
2
@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,
2
:-) ... 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 1 ... 2 N, więc i 2 a - 1 - i 2 a = A iK=2N1...2Ni2a1i2a=Ai . To kolejny dowód na kompletność mojego problemu. NP
Mohammad Al-Turkistany

Odpowiedzi:

10

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

ai...11111...

21112112111

 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×wa,b|ab|=kw

G

GG

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,