Jak trudne jest tasowanie sznurka?

Losowanie dwóch ciągów znaków polega na przeplataniu znaków w nowy ciąg znaków, utrzymując porządek znaków każdego łańcucha. Na przykład, MISSISSIPPIjest losowanie MISIPPi SSISI. Nazwijmy kwadrat ciągów, jeśli jest to tasowanie dwóch identycznych ciągów. Na przykład ABCABDCDjest kwadratowy, ponieważ jest to przetasowanie ABCDi ABCD, ale ciąg ABCDDCBAnie jest kwadratowy.

Czy istnieje szybki algorytm określający, czy łańcuch jest kwadratowy, czy trudny do NP? Oczywiste podejście do programowania dynamicznego wydaje się nie działać.

Nawet następujące przypadki szczególne wydają się trudne: (1) ciągi, w których każdy znak występuje najwyżej cztery sześć razy, oraz (2) ciągi zawierające tylko dwa różne znaki. Jak zauważa Per Austrin poniżej, specjalny przypadek, w którym każda postać występuje najwyżej cztery razy, można zmniejszyć do 2SAT.

---

Aktualizacja: ten problem ma inną formułę, która może ułatwić sprawdzenie twardości.

Rozważmy wykres G, którego wierzchołki są liczbami całkowitymi od 1 do n; zidentyfikuj każdą krawędź za pomocą rzeczywistego odstępu między jej punktami końcowymi. Mówimy, że dwie krawędzie G są zagnieżdżone, jeśli jeden przedział prawidłowo zawiera drugi. Na przykład krawędzie (1,5) i (2,3) są zagnieżdżone, ale (1,3) i (5,6) nie są, a (1,5) i (2,8) nie. Dopasowanie w G nie jest zagnieżdżone, jeśli nie ma zagnieżdżonej pary krawędzi. Czy istnieje szybki algorytm określający, czy G ma nie zagnieżdżone idealne dopasowanie, czy też jest to trudny NP?

• Odtasowywanie łańcucha jest równoznaczne ze znalezieniem idealnego dopasowania bez zagnieżdżenia w rozłącznym związku kliki (z krawędziami między równymi znakami). W szczególności rozpakowywanie łańcucha binarnego jest równoznaczne ze znalezieniem idealnego dopasowania nie zagnieżdżonego w rozłącznym połączeniu dwóch klik. Ale nawet nie wiem, czy ten problem jest trudny dla grafów ogólnych, czy łatwy dla jakichkolwiek interesujących klas grafów.

• Nie jest to łatwe algorytm wielomianowy czas, aby znaleźć idealny innych niż przekraczania skojarzeń.

---

Aktualizacja (24 czerwca 2013 r.): Problem został rozwiązany! Istnieją teraz dwa niezależne dowody, że identyfikacja ciągów kwadratowych jest NP-kompletna.

• W listopadzie 2012 r. Sam Buss i Michael Soltys ogłosili redukcję z 3-partycji , co pokazuje, że problem jest trudny nawet w przypadku ciągów znaków składających się z 9-znakowego alfabetu. Zobacz „Unshuffling a Square is NP-Hard ”, Journal of Computer System Sciences 2014.

• W czerwcu 2013 r. Romeo Rizzi i Stéphane Vialette opublikowali redukcję od najdłuższego wspólnego problemu podsekwencji . Patrz „ Rozpoznawanie słów, które są kwadratami dla losowego produktu ”, Proc. VIII Międzynarodowe Sympozjum Informatyczne w Rosji , Springer LNCS 7913, s. 235–245.

Istnieje również prostszy dowód na to, że znalezienie niedopasowanych idealnych dopasowań jest trudne dla NP, ze względu na Shuai Cheng Li i Ming Li w 2009 roku. Patrz „ O dwóch otwartych problemach wzorów 2-interwałowych ”, Theoretical Computer Science 410 (24–25 ): 2410–2423, 2009.

Michael Soltys i ja udało nam się udowodnić, że problem określania, czy ciąg może być zapisany jako tasowanie kwadratowe, jest NP kompletny. Dotyczy to nawet skończonego alfabetu zawierającego tylko różnych symboli, chociaż nasz dowód jest napisany dla alfabetu zawierającego 9 symboli. To pytanie jest nadal otwarte dla mniejszych alfabetów, powiedzmy z tylko 2 symbolami. Nie spojrzeliśmy na problem pod ograniczeniem, że każdy symbol pojawia się tylko 6 razy (lub, bardziej ogólnie, stała liczba razy); więc to pytanie jest nadal otwarte.$7$$9$$2$$6$

Dowód wykorzystuje redukcję z części. Publikacja tutaj jest zbyt długa, ale przedruk „Unshuffling a string is NP -hard” jest dostępny na naszych stronach internetowych:$3$$\text{NP}$

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

i

http://www.cas.mcmaster.ca/~soltys/#Papers .

Artykuł został opublikowany w czasopiśmie Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

W specjalnym przypadku, o którym wspominasz, gdy każda postać pojawia się maksymalnie cztery razy, następuje prosta redukcja do 2-SAT (chyba że czegoś mi brakuje ...) w następujący sposób:

Najważniejsze jest to, że dla każdej postaci istnieją (co najwyżej) dwa prawidłowe sposoby dopasowywania wystąpień postaci (trzecią możliwością będzie zagnieżdżenie). Użyj zmiennej boolowskiej, aby wskazać, które z dwóch dopasowań jest wybrane. Teraz przypisanie do tych zmiennych daje prawidłowe przetasowanie ciągu iff dla każdej pary zagnieżdżonych krawędzi, nie wybrano obu. Ten warunek można dokładnie opisać przez rozłączenie zmiennych (ewentualnie zanegowanych) odpowiadających dwóm zaangażowanym znakom.

Oto algorytm, który może mieć pewne szanse na poprawność, choć udowodnienie tego wydaje się trudne i nie postawiłbym na to domu ...

Powiedzmy, że jest czyszczone, jeśli dla każdej krawędzi e istnieje (ewentualnie zagnieżdżone) idealne dopasowanie G, które używa e i nie używa żadnej krawędzi zawartej w e lub zawierającej e .$G$$e$$G$$e$$e$

Łatwo jest sprawdzić, czy jest wyczyszczony, a jeśli nie znajduje naruszających krawędzi. Oczywiście żadna z tych naruszających krawędzi nie może być użyta w niedopasowanym idealnym dopasowaniu G , więc można je bezpiecznie usunąć z rozważań. Powtarzając ten proces, uzyskać (unikalne) przedmuchanej podgrafu z G , który ma nie zagnieżdżonej doskonałe dopasowanie IFF G ma.$G$$G$$G$$G$

Teraz następuje skok wiary, który może, ale nie musi być poprawny: mamy nadzieję, że na oczyszczonym wykresie, jeśli nadal będą wierzchołki stopnia , możemy dokonać chciwego wyboru i dopasować pierwszy taki wierzchołek do jego pierwszego sąsiada (lub równoważnie usuń krawędzie z wszystkimi pozostałymi sąsiadami).$> 1$

Po chciwym wyborze ponownie oczyszczamy wykres i tak dalej, a proces kończy się, gdy (mam nadzieję), że wykres nie pasuje do zagnieżdżenia.

Na początku myślałem, że z grubsza przypominałoby to chciwość algorytmu i nie działa, ale zaskakująco trudno było mi znaleźć kontrprzykład.

Rozwiązanie zaproponowane przez Sama Bussa w listopadzie 2012 r. (Pokazujące, że przemieszanie kwadratu w NP-twardym przez redukcję z 3 partycji) jest teraz opublikowanym artykułem w Journal of Computer System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Romeo Rizzi i Stéphane Vialette udowadniają, że rozpoznawanie ciągów kwadratowych jest NP-zupełne w artykule z 2013 r. „ Rozpoznawanie słów, które są kwadratami dla produktu losowego ”, dzięki redukcji od najdłuższego problemu podsekwencji binarnej. Twierdzą, że złożoność rozpakowywania ciągów binarnych jest nadal otwarta.

Jeszcze prostszy dowód na to, że znalezienie nienasyconego idealnego dopasowania jest NP-zupełne, podali Shuai Cheng Li i Ming Li w artykule z 2009 r. „ O dwóch otwartych problemach wzorów 2-interwałowych ”. Używają jednak terminologii odziedziczonej po bioinformatyce. Zamiast „idealnego dopasowania nie zagnieżdżonego” nazywają to „ problemem DIS-2-IP- $\{<, \between\}$ ”. Równoważność między tymi dwoma problemami opisali Blin, Fertin i Vialette :

Problem 2-IP-DIS- $\{<, \between\}$ ma natychmiastowe sformułowanie w kategoriach ograniczonych dopasowań na ogólnych wykresach: Biorąc pod uwagę wykres $G$ wraz z liniowym uporządkowaniem $\pi$ wierzchołków $G$ , 2-IP-DIS- $\{<, \between\}$ problemem jest to równoważne z ustaleniem maksymalnego dopasowania liczność $M$ w $G$ z własności, że dla dowolnych dwóch różnych krawędzi $\{u, v\}$ i $\{u', v'\}$ o $M$ ani$min \{ \pi(u), \pi(v) \} \lt min \{ \pi(u'), \pi(v') \}$ oraz$max \{ \pi(u'), \pi(v') \lt max \{ \pi(u), \pi(v) \}$ nor$min \{ \pi(u'), \pi(v') \} \lt min \{ \pi(u), \pi(v) \}$ oraz$max \{ \pi(u), \pi(v) \} \lt max \{ \pi(u'), \pi(v') \}$ występują.

Aktualizacja (25 lutego 2019 r.): Bulteau i Vialette pokazały, że problem decyzyjny polegający na odtajnieniu łańcucha binarnego jest w ich dokumencie kompletny, rozpoznawanie binarnych kwadratów losowych jest trudne .

czy to pomaga?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

NIGDY NIE UMYSŁ, TO ODPOWIEDŹ JEST ŹLE. Nie udaje się na wejściu „AABAAB”: łapczywe dopasowanie dwóch pierwszych A ze sobą uniemożliwia dopasowanie pozostałych symboli. Zostawiam to, a nie usuwam, aby pomóc innym uniknąć tego samego błędu.

Wydaje mi się, że zawsze można bezpiecznie łapać każdą kolejną postać domniemanego kwadratu łapczywie do innej równej postaci, która jest na jak najwcześniejszej pozycji. To znaczy, myślę, że następujący algorytm czasu liniowego powinien działać:

Zapętlaj każdą pozycję i w ciągu wejściowym, i = 0, 1, 2, ... n. Dla każdej pozycji i sprawdź, czy ta pozycja została już dopasowana do jakiejś wcześniejszej pozycji w ciągu. Jeśli nie, dopasuj go do znaku równości, który pojawia się po ostatniej już dopasowanej pozycji i poza tym jest możliwie najwcześniej w ciągu. Jeśli nie znaleziono dopasowania dla jakiegoś znaku, zadeklaruj, że dane wejściowe nie są kwadratem; w przeciwnym razie jest to zestaw znaków w pierwszej parze każdego dopasowania.

Oto w Pythonie:

def sqrt (S):
    mecze = []
    i, j = 0, 0
    podczas gdy i <len (S):
        if j <len (mecze) i mecze [j] [1] == i:
            i + = 1
            j + = 1
            dalej
        jeśli pasuje:
            k = dopasowania [-1] [1] + 1
        jeszcze:
            k = 1
        podczas gdy k <len (S) i S [k]! = S [i]:
            k + = 1
        jeśli k> = len (S):
            podniesienie wyjątku („To nie jest kwadrat”)
        match.append ((i, k))
        i + = 1
    return „” .join (S [a] dla a, b w meczach)

print sqrt („ABCABDCD”)

Tutaj i jest zmienną głównej pętli (pozycja, którą próbujemy dopasować), j jest wskaźnikiem w tablicy dopasowanych par, który przyspiesza sprawdzenie, czy pozycja i jest już dopasowana, a k jest indeksem używanym do wyszukiwania znak, który pasuje do tego w pozycji i. Jest to czas liniowy, ponieważ i, j i k rosną monotonicznie przez łańcuch, a każda iteracja wewnętrznej pętli zwiększa jeden z nich.

Aktualizacja: Nie ma sensu mówić o trudnościach ze znalezieniem idealnego dopasowania, które nie zagnieżdża się i nie krzyżuje, gdy etykiety mają wartość od 1 do n, ponieważ jest tylko jedna taka. (Tak, sam się kopię.) Byłoby jednak sensowne, biorąc pod uwagę większy zakres na etykietach ... więc wciąż widzę nadzieję, ale może to być zupełnie bezcelowe. Z pewnością będę musiał to kontynuować.

---

Mogę wymyślić, dlaczego może być trudno znaleźć dopasowanie, które nie zagnieżdża się i nie krzyżuje. Pozwól mi nazwać takie dopasowanie rozłącznym dopasowaniem . Nie jestem pewien, w jakim stopniu to pomaga, ale i tak przedstawię uzasadnienie. (Powinienem zauważyć, że mój argument w obecnym brzmieniu nie jest kompletny, a szczegóły, które pomijam, są prawdopodobnie kluczowe. Wyobrażam sobie jednak, że może to być początek.)

Zacznę od nieco innego problemu. Biorąc pod uwagę wykres którego krawędzie są pokolorowane za pomocą $G$$k$ kolorów, a wierzchołki są oznaczone od do n , czy istnieje rozłączne dopasowanie, które zawiera dokładnie jedną krawędź każdego koloru? Ten problem wydaje się być trudny do rozwiązania (argument jest zarówno pełny, jak i prosty - chyba że czegoś mi brakuje). Redukcja wyrzuca wykres, który jest rozłącznym związkiem klik.$1$$n$

Redukcja wynika z Disjoint Factors , problemu NP-zupełnego wprowadzonego w [1]. Przykładem czynników rozłącznych jest ciąg znaków nad alfabetem wielkości , a pytanie brzmi, czy istnieje k czynników rozłącznych, gdzie czynnik jest podłańcuchem, który zaczyna się i kończy tą samą literą; a dwa czynniki są rozłączne, jeśli nie nakładają się na ciąg (zwróć uwagę, że w szczególności „zagnieżdżanie” również jest niedozwolone).$k$$k$

Pozwól mi Oznaczmy przez , elementy k -sized alfabetu związanego z rozłącznych Factors instancji.$a_1,\ldots, a_k$$k$

Biorąc pod uwagę wystąpienie czynników rozłącznych, to znaczy, powiedzmy, ciąg długości , utwórz wykres, który ma n wierzchołków z etykietami wierzchołków od 1 do n . Dodanie od wierzchołków krawędzi w kształcie U i V , jeżeli odpowiednie pozycje mają taką samą literę (powiedzmy ı ), a także kolor krawędzi ( $n$$n$$1$$n$$u$$v$$a_i$ z kolorem i .$(u,v)$$i$

Dowód zmniejszenia wynika zasadniczo z definicji. Biorąc pod uwagę $k$ rozłącznych czynników, wyraźnie mamy rozłączne kolorowe dopasowanie, wystarczy wybrać krawędzie podane przez rozłączne czynniki i łatwo zauważyć, że wynikowe dopasowanie jest zarówno kolorowe, jak i rozłączne. I odwrotnie, jeśli istnieje k- rozłączne kolorowe dopasowanie, to mamy k czynników rozłącznych, po jednym dla każdej litery, ponieważ dopasowanie jest kolorowe (a zatem wybiera jeden czynnik na literę) i jest rozłączne (więc odpowiednie czynniki nie będą się nakładać ).$k$$k$

Aby pozbyć się kolorów i sprawić, by dopasowanie było idealne, aczkolwiek w możliwie większym zakresie , wprowadź następujące modyfikacje do tak utworzonego wykresu:

$U_a$$a$$U_a$$A$$(A-2)$$U_a$

Z grubsza mówiąc, jeśli wykres ma doprowadzić do idealnego dopasowania, nowo wprowadzone wierzchołki muszą zostać dopasowane do wierzchołków $U_a$

[1] O problemach bez jąder wielomianowych , Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows i Danny Hermelin, J. Comput. Syst. Sci.

Podejście to nie działa: rozkładanie potasowanego kwadratu przez wyjęcie dwóch pasujących liter nie powoduje przetasowania kwadratów ... Zobacz komentarze Radu poniżej.

---

$\Sigma$

$${\small \begin{aligned} S(XY)&\Rightarrow A(X,Y)&(1)\newline A(aX_1, aX_2Y_1Y_2)&\Rightarrow A(X_1,Y_1)\,A(X_2,Y_2)&(2)\newline A(\varepsilon,\varepsilon)&\Rightarrow\varepsilon&(3) \end{aligned}}$$ $a$$\Sigma$$\varepsilon$ oznacza pusty.

$X_1$$Y_1$$Y_1$$X_2$$Y_2$$Y_1$$Y_2$$X_1$$X_2$

$abcabdcd$

$${\small\begin{aligned} S(abcabdcd) &\Rightarrow A(abc, abdcd) &(\text{by } 1, X=abc, Y=abdcd)\newline &\Rightarrow A(bc,bdcd)\,A(\varepsilon,\varepsilon)&(\text{by } 2, X_1=bc, Y_1=bdcd, X_2=Y_2=\varepsilon)\newline &\Rightarrow A(c,c)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(d,d)\,A(\varepsilon,\varepsilon)&(\text{by } 3)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)\,A(\varepsilon,\varepsilon)&(\text{by } 2)\newline &\Rightarrow^3\varepsilon&\text{i.e. success} \end{aligned}}$$

$0011$

$${\small\begin{aligned} S(0011)&\Rightarrow A(0,011)\newline &\Rightarrow A(\varepsilon,\varepsilon)\,A(1,1)\newline &\Rightarrow A(1,1)\newline &\Rightarrow^\ast \varepsilon \end{aligned}}$$

$X$$Y$

Aktualizacja: Jak zauważa Tsuyoshi Ito w komentarzach, algorytm ten ma wykładniczy czas działania.

Oryginalny post:

Oto jak zaprogramowałbym to w świecie rzeczywistym.

Otrzymujemy ciąg S = (S [1], ..., S [n]). Dla każdego prefiksu S_r = (S [1], ..., S [r]) istnieje zestaw {(T_i, U_i)} par ciągów znaków, taki że S_r jest przetasowaniem (T_i, U_i), a T_i jest prefiksem U_i (tj. U_i 'zaczyna się od' T_i). Sam S_r jest kwadratem wtedy i tylko wtedy, gdy ten zestaw zawiera parę (T_i, U_i) z T_i = U_i.

Teraz nie musimy generować wszystkich tych par; musimy tylko wygenerować przyrostek V_i każdego łańcucha U_i uzyskany przez usunięcie jego kopii T_i. Wyeliminuje to (prawdopodobnie wykładniczą) liczbę nieistotnych duplikatów. Teraz S_r jest kwadratem wtedy i tylko wtedy, gdy ten zestaw sufiksów zawiera pusty ciąg. Algorytm staje się:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Na przykład, jeśli S to AABAAB:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Możemy odrzucić wszystkie przyrostki o ponad połowę dłuższe niż łańcuch wejściowy, co upraszcza:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

Zaprogramowałem to w C ++ i działa na wszystkich podanych tu przykładach. Mogę opublikować kod, jeśli ktoś jest zainteresowany. Pytanie brzmi: czy rozmiar SuffixSet może rosnąć szybciej niż wielomianowo?

EDYCJA: To jest niepoprawna odpowiedź.

---

Sylvain zasugerował RCG, który niestety nie był odpowiedni dla tych „losowych kwadratów”. Myślę jednak, że istnieje jeden (EDYCJA: nie RCG, patrz komentarze Kurta poniżej!) , Który wygląda następująco:

$\begin{aligned} S(Y) & \rightarrow A(\epsilon,Y) & (1) \newline A(X, ZY) & \rightarrow A(XZ,Y) & (2) \newline A(aX, aY) & \rightarrow A(X,Y) \quad \text{ for every } a \in \Sigma & (3) \newline A(\epsilon,\epsilon) & \rightarrow \epsilon & (4) \end{aligned}$

$a$$a'$$b$$b'$$a \prec b$$a' \prec b'$$\prec$$(1,2)$$(3)$$(2)$

$100110101010$

$\begin{aligned} S(100110101010) & \Rightarrow A(\epsilon,100110101010) & (1) \newline & \Rightarrow A(1001,10101010) & (2) \newline & \Rightarrow^* A(01,101010) & (3) \newline & \Rightarrow A(011,01010) & (2) \newline & \Rightarrow^* A(1,010) & (3) \newline & \Rightarrow A(10,10) & (2) \newline & \Rightarrow^* A(\epsilon, \epsilon) & (3) \newline & \Rightarrow \epsilon & (4) \end{aligned}$

Nie opracowałem formalnego dowodu, że ta gramatyka rzeczywiście przechwytuje dokładnie „losowe kwadraty”, ale nie powinno to być zbyt trudne. Sylvain wspomniał już, że problem decyzyjny dla RCG jest wielomianowy.