Testowanie, czy litery można zaplanować, aby uzyskać słowo w zwykłym języku

I ustalić język regularny na alfabetem , i rozważmy następujący problem, który ja nazywam się harmonogram dla . Nieoficjalnie, dane wejściowe dają mi liter i odstępy dla każdej litery (tj. Minimalną i maksymalną pozycję), a moim celem jest umieszczenie każdej litery w tym przedziale, tak aby żadne dwie litery nie były odwzorowane na tę samą pozycję i aby Otrzymany -letter słowo jest . Formalnie:$L$$\Sigma$$L$$n$$n$$L$

• Wejściowe: trójek gdzie i są liczbami całkowitymi$n$$(a_i, l_i, r_i)$$a_i \in \Sigma$$1 \leq l_i \leq r_i \leq n$
• Dane wyjściowe: czy istnieje bijection taki, że l_i \ leq f (i) \ leq r_i dla wszystkich i , a a_ {f ^ {- 1} (1)} \ cdots a_ {f ^ {- 1} (n)} \ wl .$f: \{1, \ldots, n\} \to \{1, \ldots, n\}$$l_i \leq f(i) \leq r_i$$i$$a_{f^{-1}(1)} \cdots a_{f^{-1}(n)} \in L$

Oczywiście ten problem dotyczy NP, odgadując bijection $f$ i sprawdzając członkostwo w $L$ w PTIME. Moje pytanie: Czy istnieje zwykły język $L$ taki że problem planowania liter dla $L$ jest trudny do NP?

Kilka wstępnych obserwacji:

• Wydaje się, że podobne problemy były badane podczas planowania: mogliśmy postrzegać ten problem jako planowanie zadań kosztu jednostkowego na jednym komputerze, przy jednoczesnym przestrzeganiu dat początkowych i końcowych. Jednak ten ostatni problem dotyczy oczywiście PTIME z zachłannym podejściem i nie widzę nic w literaturze dotyczącej harmonogramu w przypadku, gdy zadania są oznaczone i chcielibyśmy uzyskać słowo w docelowym języku regularnym.
• Jeden inny sposób, aby zobaczyć ten problem jest tak szczególnym przypadku dwustronnego problemu maksimum dopasowania (między literami i stanowisk), ale znowu to trudno wyrazić ograniczenie, że musimy wpaść w $L$ .
• W konkretnym przypadku, gdy $L$ jest językiem formy $u^*$ dla jakiegoś ustalonego słowa $u$ (np. $(ab)^*$ ), wówczas problem z szeregowaniem liter dla $L$ występuje w czasie PTIME z łatwym, chciwym algorytmem: zbuduj słowo z od lewej do prawej i umieść na każdej pozycji jedną z dostępnych liter, która jest poprawna względem $L$ i ma najmniejszy czas $r_i$ . (Jeśli nie ma dostępnych liter, które są poprawne, nie powiodą się.) Jednak nie uogólnia to na dowolne zwykłe języki $L$ ponieważ dla takich języków możemy mieć wybór, jakiego rodzaju litery użyć.
• Wygląda na to, że algorytm dynamiczny powinien działać, ale w rzeczywistości nie jest to takie proste: wydaje się, że musisz zapamiętać, który zestaw liter wziąłeś do tej pory. Rzeczywiście, budując słowo od lewej do prawej, kiedy osiągniesz pozycję $i$ , twój stan zależy od tego, jakie litery spożyłeś do tej pory. Nie można zapamiętać całego zestawu, ponieważ wówczas wystąpiłoby wykładniczo wiele stanów. Ale nie jest tak łatwo go „streścić” (np. Ile kopii każdego listu zostało użytych), ponieważ aby wiedzieć, które kopie wykorzystałeś, wydaje się, że musisz pamiętać, kiedy je spożyłeś (później wykorzystałeś im więcej listów było dostępnych). Nawet z językiem takim jak $(ab|ba)^*$ ,a b b $ab$ i kiedy powinieneś wybrać zależności od tego, które litery będą potrzebne później i kiedy litery będą dostępne.$ba$
• Ponieważ jednak zwykły język jest poprawiony i nie może zapamiętać tak dużej ilości informacji, mam trudności ze znalezieniem trudnego dla NP problemu, który można by zmniejszyć.$L$

Problem jest trudny NP dla gdzie jest skończonym językiem zawierającym następujące słowa:L = A ∗$L = A^*$$A$

• $x111$ , ,$x000$
• $y100$ , , ,Y 010 Y $y010$$y001$
• $00c11$ , , i01 c 10 10 c 01 11 c $01c10$$10c01$$11c00$

Zmniejszenie wynika z problemu Orientacja grafów, która jest znana z NP-trudnych (patrz https://link.springer.com/article/10.1007/s00454-017-9884-9 ). W tym problemie otrzymujemy 3-regularny niekierowany wykres, na którym każdy wierzchołek jest oznaczony „ ” lub „ ”. Celem jest takie ukierunkowanie krawędzi wykresu, aby wierzchołek każdego wierzchołka znajdował się w zestawie oznaczającym ten wierzchołek.{ 1 } { 0 , 3 $\{1\}$$\{0,3\}$

Redukcja musi przyjąć jako dane wejściowe instancję Graph Orientation i utworzyć listę potrójnych danych wyjściowych. W tej redukcji, trzykrotności, które wyprowadzamy, zawsze spełniają pewne ograniczenia. Te ograniczenia są wymienione poniżej, a my odniesiemy się do listy potrójnych jako ważnych wtedy i tylko wtedy, gdy spełniają one te ograniczenia:

• Znaki , i mają tylko interwały zawierające dokładnie jeden indeks. Innymi słowy, za każdym razem, gdy te postacie są umieszczane, są one umieszczane w określonych lokalizacjach.$x$$y$$c$
• Dla każdej potrójnej obecnej w instancji z również potrójna .$(i, l, r)$$i \in \{0,1\}$$(1-i, l, r)$
• Jeśli oba i są w tej instancji trójkami, wówczas albo , albo lub z .$(\alpha, l, r)$$(\alpha',l',r')$$l < l' \le r' < r$$l' < l \le r < r'$$\{\alpha,\alpha'\} = \{0,1\}$$l = l' < r = r'$
• Jeśli jest potrójne, to liczba trójek z wynosi dokładnie r - l + 1 .$(\alpha, l, r)$$(\alpha', l', r')$$l \le l' \le r' \le r$$r-l+1$

Zwróć uwagę na następujący lemat, udowodniony na końcu tego postu.

Lemat: dla prawidłowej listy potrójnych znaki x , i muszą być umieszczone dokładnie tak, jak wskazano przez potrójne, i dla dowolnej pary potrójnych ( 0 , l , r ) i ( 1 , l , $x$$y$$c$$(0, l, r)$ ) The dwa znaki dla tej potrójnej muszą być umieszczone przy indeksach l i r .$(1, l, r)$$l$$r$

Zatem idea redukcji jest następująca.

Używamy par potrójnych ( 0 , l , r ) i ( 1 , l , r ) do reprezentowania krawędzi. Krawędź przechodzi między punktami końcowymi o indeksie 1 i indeksie r . Zakładając, że wytwarzają ważne listę trójek, postacie z tych trójek muszą być umieszczone na L i R , więc można traktować kolejność, w jakiej umieszczone są jako wskazanie kierunku krawędzi. Tutaj 1 to „głowa” krawędzi, a 0 to „ogon”. Innymi słowy, jeśli 1 jest umieszczone na $(0, l, r)$$(1, l, r)$$l$$r$$l$$r$$1$$0$$1$$r$wtedy krawędź wskazuje od l do r, a jeśli 1 jest umieszczona w l, wówczas krawędź wskazuje od r do l .$l$$r$$1$$l$$r$$l$

Aby przedstawić wierzchołki, umieszczamy znak x lub y w indeksie i używamy trzech kolejnych znaków jako punktów końcowych trzech krawędzi, które dotykają wierzchołka. Zauważ, że jeśli umieścić X , wszystkie trzy krawędzie na wierzchołku musi zwrócić się w tym samym kierunku (wszystko na wierzchołku lub wszystko z wierzchołka), po prostu ze względu na ciągi znaków, które są w skończonej języka A . Takie wierzchołki mają outdegree 0 lub 3 , więc umieścić X dokładnie do wierzchołków oznaczonych { $x$$y$$x$$A$$0$$3$$x$ , 3 } . Jeśli umieścimy$\{0,3\}$$y$Dokładnie jeden z trzech krawędziach w punkcie vertex musi w tym samym kierunku, ze względu na ciągi w A . Takie wierzchołki mają przeciążenie 1 , więc umieszczamy y dokładnie dla wierzchołków oznaczonych { 1 } .$A$$1$$y$$\{1\}$

W pewnym sensie jesteśmy skończeni. W szczególności zgodność między rozwiązaniem tego wystąpienia a rozwiązaniem wystąpienia Orientacja graficzna powinna być jasna. Niestety lista produkowanych przez nas trójek może być nieprawidłowa, dlatego opisane „krawędzie” mogą nie działać zgodnie z przeznaczeniem. W szczególności lista potrójnych może nie być ważna, ponieważ warunek, że odstępy od potrójnych zawsze muszą się wzajemnie zawierać, może się nie utrzymywać: odstępy między dwiema krawędziami mogą zachodzić na siebie bez jednego zawierającego drugie.

Aby temu przeciwdziałać, dodajemy trochę infrastruktury. W szczególności dodajemy „wierzchołki skrzyżowane”. Krzyżujący się wierzchołek to wierzchołek stopnia 4, którego krawędzie są sparowane tak, że w obrębie każdej pary jedna krawędź musi wskazywać na wierzchołek krzyżujący się, a druga na zewnątrz. Innymi słowy, wierzchołek skrzyżowania będzie zachowywał się tak samo, jak tylko dwie „krzyżujące się” krawędzie. Reprezentujemy wierzchołek skrzyżowania, umieszczając znak c w pewnym indeksie i . Następnie zauważ, że język A ogranicza znaki w i - 1 i i + 2, aby były przeciwne (jeden 0 i jeden 1 oraz $4$$c$$i$$A$$i-1$$i+2$$0$$1$ ) oraz znaki w $i-2$ + 1, aby być odwrotnie. Tak więc, jeśli użyjemy tych wskaźników jako punktów końcowych dla czterech krawędzi w wierzchołku skrzyżowania, zachowanie będzie dokładnie takie, jak opisano: cztery krawędzie są w parach, a pomiędzy każdą parą jeden wskazuje i jeden wskazuje.$i+1$

Jak faktycznie umieszczamy te zwrotnice? Załóżmy, że mamy dwa przedziały ( l , r ) i ( l ' , r ' ), które się nakładają. WLOG, l < l ′ < r < r ′ . Dodajemy znak crossover na środku (między l ′ i r ). (Powiedzmy, że cały czas rozmieszczaliśmy wszystko tak daleko, że zawsze jest wystarczająco dużo miejsca, a na końcu usuwamy wszelkie niewykorzystane miejsce.) Niech indeks znaku skrzyżowania będzie równy $(l, r)$$(l', r')$$l < l' < r < r'$$l'$$r$$i$ . Następnie zastępujemy cztery tróje ( 0, l , r ) , ( 1 , l , r ) , ( 0 , l ′ , r ′ ) , i ( 1 , l ′ , r ′ ), z ośmioma potrójnymi liczbami po dwie (każda o znaku 0 i jedna o znaku 1 ) dla następujących czterech przedziałów ( l , i - 1 ) , ( i + 2 , r $(0, l, r)$$(1, l, r)$$(0, l', r')$$(1, l', r')$$0$$1$$(l, i-1)$$(i+2, r)$ , ( l ′ , i -2 ) , ( i + 1 , r ' ) . Zauważ, że interwały nie pokrywają się już w zły sposób! (Po tej zmianie, jeśli dwa przedziały nachodzą na siebie, jeden jest ściśle wewnątrz drugiego.) Ponadto krawędź od l do r jest zastępowana krawędzią od$(l', i-2)$$(i+1, r')$$l$$r$$l$ do wierzchołka skrzyżowania, a następnie krawędzią stamtąd do r ; te dwie krawędzie są sparowane na wierzchołku skrzyżowania w taki sposób, że jedna jest skierowana do drugiej, a druga wskazana; innymi słowy, dwie krawędzie razem zachowują się tak samo jak jedna, którą zastępują.$r$

W pewnym sensie umieszczenie w tym skrzyżowanym wierzchołku „nie skrzyżowanych” dwóch krawędzi (których przedziały zachodziły na siebie). Łatwo zauważyć, że dodanie wierzchołka skrzyżowania nie może spowodować skrzyżowania dodatkowych krawędzi. W ten sposób możemy odkryć każdą parę przecinających się krawędzi, wstawiając wystarczającą liczbę skrzyżowanych wierzchołków. Wynik końcowy nadal odpowiada instancji Graph Orientation, ale teraz lista potrójnych jest poprawna (wszystkie właściwości są łatwe do zweryfikowania teraz, gdy „nie skrzyżowaliśmy” żadnych przecinających się krawędzi), więc zastosowanie ma lemat, krawędzie muszą zachowywać się zgodnie z opisem , a korespondencja jest tak naprawdę równoważnością. Innymi słowy, ta redukcja jest poprawna.

dowód lematu

Lemat: dla prawidłowej listy trójek, znaki x , y i C musi być umieszczony tak, jak wskazano przez trójek, a dla dowolnej pary trójek ( 0 , l , r ) i ( 1 , l , r ) The dwa znaki dla tej potrójnej muszą być umieszczone przy indeksach l i r .$x$$y$$c$$(0, l, r)$$(1, l, r)$$l$$r$

dowód:

Kontynuujemy przez indukcję potrójnej długości przedziału. W szczególności nasze stwierdzenie jest następujące: dla każdego k, jeśli jakiś potrójny ma przedział długości k, znak w tej potrójnej musi być umieszczony zgodnie z opisem w lemacie.$k$$k$

Przypadek podstawowy: dla k = 0 potrójne musi umieszczać znak x , y lub c pod jednym indeksem w przedziale. Jest to dokładnie tak, jak opisano w lemacie.$k = 0$$x$$y$$c$

Przypadek indukcyjny: załóżmy, że wyrażenie zachowuje dla dowolnego k mniejszego niż niektóre k ′ . Teraz rozważmy trzykrotnie o długości przedziału k ′ . Wtedy ta potrójna musi być w postaci ( i , l , r ) z r = l + k ′ - 1 i i ∈ { 0 , 1 } . Potrójne ( 1 - i , l , r ) również muszą być obecne. Liczba trójek ( $k$$k'$$k'$$(i, l, r)$$r = l+k'-1$$i \in \{0,1\}$$(1-i, l, r)$ ′ , L ′ , r ′ ) przy l ≤ l ′ ≤ r ′ ≤ r wynosi dokładnie r - l + 1 = k ′ . Te tróje obejmują tróje ( 0 , 1 , r ) i ( 1 , 1 , r ), ale także k - - 2 inne tróje postaci ( α ′ , l $(\alpha',l',r')$$l \le l'\le r' \le r$$r-l+1 = k'$$(0, l, r)$$(1, l, r)$$k'-2$, r ′ ) przy l < l ′ ≤ r ′ < r . Te wszystkie trzy tróje mają długość przedziału mniejszą niż k ′ , więc wszyscy muszą umieścić swoje znaki, jak określono w lemacie. Jedynym sposobem na to jest to, że te potrójne umieszczają znaki w każdym indeksie, zaczynając od indeksu l + 1 i kończąc na indeksie r + 1 . Zatem nasze dwie trzy ( 0 , 1 , r ) i ( 1 , 1 , r $(\alpha',l',r')$$l < l' \le r' < r$$k'$$l+1$$r+1$$(0, l, r)$$(1, l, r)$ must place their characters at indices $l$ and $r$, as described in the lemma, concluding the inductive case.

By induction, the lemma is correct.

@MikhailRudoy was the first to show NP-hardness, but Louis and I had a different idea, which I thought I could outline here since it works somewhat differently. We reduce directly from CNF-SAT, the Boolean satisfiability problem for CNFs. In exchange for this, the regular language $L$ that we use is more complicated.

The key to show hardness is to design a language $L'$ that allows us to guess a word and repeat it multiple times. Specifically, for any number $k$ of variables and number $m$ of clauses, we will build intervals that ensure that all words $w$ of $L'$ that we can form must start with an arbitrary word $u$ of length $k$ on alphabet $\{0, 1\}$ (intuitively encoding a guess of the valuation of variables), and then this word $u$ is repeated $m$ times (which we will later use to test that each clause is satisfied by the guessed valuation).

To achieve this, we will fix the alphabet $A = \{0, 1, \#, 0', 1'\}$ and the language: $L' := (0|1)^* (\# (00'|11')^*)^* \# (0|1)^*$. The formal claim is a bit more complicated:

Claim: For any numbers $k, m \in \mathbb{N}$, we can build in PTIME a set of intervals such that the words in $L'$ that can be formed with these intervals are precisely:

where $\tilde{u}$ denotes the result of reversing the order of $u$ and swapping $0$'s and $1$'s, where $u'$ denotes the result of adding a prime to all letters in $u$, and where $x \bowtie y$ for two words $x$ of $y$ of length $p$ is the word of length $2p$ formed by taking alternatively one letter from $x$ and one letter from $y$.

Here's an intuitive explanation of the construction that we use to prove this. We start with intervals that encode the initial guess of $u$. Here is the gadget for $n = 4$ (left), and a possible solution (right):

It's easy to show the following observation (ignoring $L'$ for now): the possible words that we can form with these intervals are exactly $u \# \tilde{u}$ for $u \in \{0, 1\}^k$. This is shown essentially like the Lemma in @MikhailRudoy's answer, by induction from the shortest intervals to the longest ones: the center position must contain $\#$, the two neighboring positions must contain one $0$ and one $1$, etc.

We have seen how to make a guess, now let's see how to duplicate it. For this, we will rely on $L'$, and add more intervals. Here's an illustration for $k = 3$:

For now take $L := (0|1)^* (\# (00'|11')^*)^* \# (0' | 1')^*$. Observe how, past the first $\#$, we must enumerate alternatively an unprimed and a primed letter. So, on the un-dashed triangle of intervals, our observation above still stands: even though it seems like these intervals have more space to the right of the first $\#$, only one position out of two can be used. The same claim holds for the dashed intervals. Now, $L$ further enforces that, when we enumerate an unprimed letter, the primed letter that follows must be the same. So it is easy to see that the possible words are exactly: $u \# (\tilde{u} \bowtie \tilde{u}') \# u'$ for $u \in \{0, 1\}^k$.

Now, to show the claim, we simply repeat this construction $m$ times. Here's an example for $k=3$ and $m=2$, using now the real definition of $L'$ above the statement of the claim:

As before, we could show (by induction on $m$) that the possible words are exactly the following: $u (\# \tilde{u} \bowtie \tilde{u}' \# u \bowtie u')^2 \# \tilde{u}$ for $u \in \{0, 1\}^k$. So this construction achieves what was promised by the claim.

Thanks to the claim we know that we can encode a guess of a valuation for the variables, and repeat the valuation multiple times. The only missing thing is to explain how to check that the valuation satisfies the formula. We will do this by checking one clause per occurrence of $u$. To do this, we observe that without loss of generality we can assume that each letter of the word is annotated by some symbol provided as input. (More formally: we could assume that in the problem we also provide as input a word $w$ of length $n$, and we ask whether the intervals can form a word $u$ such that $w \bowtie u$ is in $L$.) The reason why we can assume this is because we can double the size of each interval, and add unit intervals (at the bottom of the picture) at odd positions to carry the annotation of the corresponding even position:

Thanks to this observation, to check clauses, we will define our regular language $L$ to be the intersection of two languages. The first language enforces that the sub-word on even positions is a word in $L'$, i.e., if we ignore the annotations then the word must be in $L'$, so we can just use the construction of the claim and add some annotations. The second language $L''$ will check that the clauses are satisfied. To do this, we will add three letters in our alphabet, to be used as annotations: $+$, $-$, and $\epsilon$. At clause $1 \leq i \leq m$, we add unit intervals to annotate by $+$ the positions in the $i$-th repetition of $u$ corresponding to variables occurring positively in clause $i$, and annotate by~$-$ the positions corresponding to negatively occurring variables. We annotate everything else by~$\epsilon$. It is now clear that $L''$ can check that the guessed valuation satisfies the formula, by verifying that, between each pair of consecutive $\#$ symbols that contain an occurrence of $u$ (i.e., one pair out of two), there is some literal that satisfies the clause, i.e., there must be one occurrence of the subword $+1$ or of the subword $-0$.

This concludes the reduction from CNF-SAT and shows NP-hardness of the letter scheduling problem for the language $L$.