Effizienter Algorithmus für das Vorhandensein von Permutation mit Differenzenfolge?

Diese Frage wird durch diesen Beitrag motiviert: Können Sie die Summe von zwei Permutationen in der Polynomzeit identifizieren? und mein Interesse an rechnerischen Eigenschaften von Permutationen.

Eine Differenzsequenz $a_1, a_2, \ldots a_n$ einer Permutation $\pi$ der Zahlen $1, 2, \ldots n+1$ wird gebildet, indem die Differenz zwischen jeweils zwei benachbarten Zahlen in der Permutation $\pi$ . Mit anderen Worten, $a_i= |\pi(i+1)-\pi(i)|$ für $1 \le i \le n$

Beispielsweise ist Sequenz die Differenzsequenz der Permutation . Während die Sequenzen und nicht die Differenzsequenz einer Permutation der Zahlen . $1, 1, 3$ $2 3 4 1$ $2, 2, 3$ $3, 1, 2$ $1, 2, 3, 4$

Gibt es einen effizienten Algorithmus, um zu bestimmen, ob eine bestimmte Sequenz die Differenzsequenz für eine Permutation ist oder ob sie NP-hart ist? $\pi$

BEARBEITEN : Wir erhalten rechnerisch äquivalentes Problem, wenn wir das Problem unter Verwendung von zirkulären Permutationen formulieren.

EDIT2 : Cross posted on MathOverflow, Wie schwer ist es, eine Permutation aus ihrer Differenzsequenz zu rekonstruieren?

EDIT3 hat die Prämie für die Proofskizze vergeben, und ich würde die Antwort nach Erhalt des vollständigen formalen Proofs akzeptieren.

EDIT 4 : Marzio ist schön -completeness Beweis ist erschienen in der Electronic Journal of Kombinatorik . $NP$

cc.complexity-theory co.combinatorics np-hardness permutations Mohammad Al-Turkistany
quelle

Vielleicht ist ein anderer trivialer (aber vernünftigerer?) Kommentar, dass, wenn das

eine Permutation von

(alle Werte sind verschieden), das Problem darin besteht, zu überprüfen, ob die Sequenz eine anmutige Beschriftung der Zeile von

Knoten, der in Polynomzeit lösbar ist.

a_{i}

$a_i$

[1.. n]

$[1..n]$

n + 1

$n+1$

Marzio De Biasi

@MarzioDeBiasi Ich glaube, Sie teilen meine Leidenschaft für Permutationsprobleme. Ich hoffe, dass ich das einfachste rechnerisch interessante Permutationsproblem gefunden habe :)

Mohammad Al-Turkistany

:-) ... Ich würde eher sagen, dass mein Kommentar direkt aus den Stunden stammt, die ich vergeblich mit dem Problem der anmutigen Baumkennzeichnung verbracht habe. Wenn es mir gelingt, es zu formalisieren, schreibe ich eine Antwort.

Marzio De Biasi

@MarzioDeBiasi Ich fand diesen interessanten Kommentar von Shor, der besagt, dass Ihr Problem, die Auftragsplanung mit einem Engpassproblem , einem Sonderfall meines Problems entspricht. Hier ist Shors Kommentar: Wenn

, ist das Problem äquivalent zu einer Permutation von

so dass

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$ . Dies liefert einen weiteren Beweis für die

-completeness meines Problems.

N P

$NP$

Mohammad Al-Turkistany

Antworten:

Dies ist eine Skizze einer möglichen Reduktion, um zu beweisen, dass es NP-schwer ist:

$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)

Die Löcher müssen im Rest der Permutation gefüllt sein .

3) Verwenden einer ausreichend großen 1SEQ, gefolgt von einer 1SEQ mit einigen Löchern, gefolgt von einer weiteren großen 1SEQ, um eine erzwungene Linie aufzubauen ;

4) Wenn Sie viele erzwungene Linien zusammenfügen, können Sie ein Permutationsgitterdiagramm erstellen, in dem die Knoten den fehlenden Zahlen in der zugrunde liegenden erzwungenen Permutation entsprechen.

Beispielsweise erzwingt die Sequenz 111111111211111111121111111 das folgende 5 x 7-Permutationsgitterdiagramm:

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) Sie können alle Löcher füllen (dh die Permutation vervollständigen), wenn der ursprüngliche Gittergraph einen Hamilton-Zyklus hat

EDIT: 27. Juli 2013

Ich habe versucht, die NP-Vollständigkeit des Problems offiziell zu beweisen: Ich habe ein neues Problem ( Crazy Frog-Problem ) eingeführt, nämlich den NPC. Das Permutationsrekonstruktionsproblem aus Differenzen entspricht dem "1-D Crazy Frog-Problem ohne blockierte Zellen" (das auch NPC ist).

Für die Details der Reduktion siehe meine Frage / Antwort auf cstheory "Two Hamiltonian Path Varianten" oder laden Sie einen Entwurf des Beweises "Wenn ein Frosch auf eine Permutation trifft " herunter :)) (Ich überprüfe / vervollständige ihn noch)

Marzio De Biasi
quelle

Schön, ich bin mir sicher, dass dies zu einer Lösung führen wird, das Auswahl-Gadget ist definitiv realisierbar.

Domotorp

@domotorp: Ich habe es gepostet (ich werde die Details zum ausgewählten / synchronisierten Teil in den nächsten Tagen veröffentlichen). Vielleicht enthält es einen Fehler, den ich nicht sehe, aber ich wette 1 $ , dass die gesamte Reduzierung stark vereinfacht werden kann :-)

Marzio De Biasi

@ MarzioDeBiasi Schöne Visualisierung. Sie scheinen auf dem richtigen Weg zu sein. Könnten Sie bitte Ihre Antwort auf MathOverflow posten, da das Interesse an dem Problem beträchtlich ist?

Mohammad Al-Turkistany

@MarzioDeBiasi Könnten Sie Ihre endgültige Antwort (förmlich) veröffentlichen, bevor das Kopfgeld abläuft?

Mohammad Al-Turkistany

@ MohammadAl-Turkistany: Ich bin gerade von einer Reise zurückgekehrt und werde versuchen, die Geräte in den nächsten Tagen zu formalisieren (und bei einem CSP nachzufragen).

Marzio De Biasi