Tester si les lettres peuvent être programmées pour obtenir un mot dans une langue régulière

23

Je fixe un langage régulier sur un alphabet , et je considère le problème suivant que j'appelle la planification de la lettre pour . De manière informelle, l'entrée me donne lettres et un intervalle pour chaque lettre (c'est-à-dire une position minimale et maximale), et mon objectif est de placer chaque lettre dans son intervalle de telle sorte qu'il n'y ait pas deux lettres mappées à la même position et de sorte que le résultant mot -lettre est dans . Officiellement:LLΣΣLLnnnnLL

  • Entrée: nn triplets ( a i , l i , r i )(ai,li,ri)a iΣaiΣ et 1 l ir in1lirin sont des entiers
  • Sortie: existe-t-il une bijection f : { 1 , , n } { 1 , , n }f:{1,,n}{1,,n} telle que l if ( i ) r ilif(i)ri pour tout ii , et a f - 1 ( 1 )a f - 1 ( n )Laf1(1)af1(n)L .

Évidemment, ce problème est dans NP, en devinant une bijection ff et en vérifiant l'appartenance à LL dans PTIME. Ma question: existe-t-il un langage régulier LL tel que le problème de programmation de lettres pour LL est NP-difficile?

Quelques premières observations:

  • Il semble que des problèmes similaires aient été étudiés dans la planification: nous pourrions voir le problème comme la planification de tâches à coût unitaire sur une seule machine tout en respectant les dates de début et de fin. Cependant, ce dernier problème est évidemment dans PTIME avec une approche gourmande, et je ne vois rien dans la littérature de planification pour le cas où les tâches sont étiquetées et nous voudrions obtenir un mot dans une langue régulière cible.
  • Une autre façon de voir le problème est comme un cas particulier d'un problème de correspondance maximum bipartites (entre les lettres et les positions), mais encore une fois il est difficile d'exprimer la contrainte que nous devons tomber en LL .
  • Dans le cas spécifique où LL est une langue de la forme u u pour un mot fixe uu (par exemple, ( a b ) (ab) ), alors le problème d'ordonnancement des lettres pour LL est dans PTIME avec un algorithme gourmand facile: construisez le mot à partir de la gauche à droite, et mettez à chaque position l'une des lettres disponibles qui est correcte par rapport à LL et qui a le plus petit temps r iri . (S'il n'y a pas de lettres disponibles qui sont correctes, échouent.) Cependant, cela ne se généralise pas aux langues régulières arbitraires LL car pour ces langues, nous pouvons avoir le choix du type de lettre à utiliser.
  • Il semble qu'un algorithme dynamique devrait fonctionner, mais en fait ce n'est pas si simple: il semble que vous auriez besoin de mémoriser le jeu de lettres que vous avez pris jusqu'à présent. En effet, lors de la construction d'un mot de gauche à droite, lorsque vous avez atteint une position ii , votre état dépend des lettres que vous avez consommées jusqu'à présent. Vous ne pouvez pas mémoriser l'ensemble entier car il y aurait alors de nombreux états exponentiels. Mais ce n'est pas si facile de la "résumer" (par exemple, par combien de copies de chaque lettre ont été utilisées), car pour savoir quelles copies vous avez utilisées, il semble que vous devez vous rappeler quand vous les avez consommées (plus tard vous en avez consommé les plus de lettres étaient disponibles). Même avec une langue comme ( a b | b a ) (ab|ba), il peut déjà y avoir des contraintes compliquées sur le moment où vous devez choisir de prendre un bab et quand vous devez choisir de prendre b aba selon les lettres dont vous aurez besoin plus tard et quand les lettres deviendront disponibles.
  • Cependant, comme le langage régulier LL est fixe et ne peut pas mémoriser autant d'informations, j'ai du mal à trouver un problème NP-difficile à partir duquel je pourrais réduire.
a3nm
la source
Pouvez-vous obtenir NP-complétude pour certains L dans PTIME?
Lance Fortnow
3
@LanceFortnow Bien sûr. Vous pouvez remplir un 3CNF afin que chaque variable apparaisse dans un nombre pair de littéraux et que toutes les deux occurrences consécutives soient annulées. Encodez x i en 0 i ou 1 i , puis dans l'instance d'ordonnancement des lettres, les symboles ( , ) , , sont fixes tandis que les autres sont à moitié 0 et à moitié 1 . En temps polynomial, on peut vérifier si la chaîne code pour un 3CNF rembourré qui est évalué comme vrai. xi0i1i(,),,01
Willard Zhan
Vous pouvez également généraliser le problème aux "positions arbitraires" (non limitées à 1..n). Il est peut-être plus facile de prouver la dureté (si elle est difficile).
Marzio De Biasi
@MarzioDeBiasi: Je ne suis pas sûr de comprendre, voulez-vous dire que la position des lettres pourrait être un sous-ensemble arbitraire plutôt qu'un intervalle? Je ne sais pas si c'est difficile (cela commence à ressembler un peu au problème de correspondance parfaite exacte ), mais la version avec intervalles permet un algorithme gourmand lorsque L = u donc j'ai un peu d'espoir que cela pourrait être plus facile. L=u
a3nm
@ a3nm: non, je veux dire que vous pouvez généraliser la suppression de la contrainte r in ; vous demandez un mot dans L dans lequel il y a au moins une lettre a i dans la plage [ l i . . r i ] ; en d'autres termes, vous ne "construisez" pas le mot complet de longueur n , mais vous demandez un mot de longueur arbitraire contenant les lettres données dans les plages autorisées. Je ne sais pas si cela change la complexité du problème, mais dans ce cas, vous devez faire face à des "index" qui ne sont peut-être pas liés polynomialement par la longueur de l'entrée. rinai[li..ri]n
Marzio De Biasi

Réponses:

7

Le problème est NP-difficile pour L = A A est le langage fini contenant les mots suivants:L=AA

  • x 111 , x 000 ,x111x000
  • y 100 , y 010 , y 001 ,y100y010y001
  • 00 c 11 , 01 c 10 , 10 c 01 et 11 c 0000c1101c1010c0111c00

La réduction provient du problème d'orientation du graphique, qui est connu pour être NP-difficile (voir https://link.springer.com/article/10.1007/s00454-017-9884-9 ). Dans ce problème, on nous donne un graphe non orienté à 3 régularités dans lequel chaque sommet est étiqueté " { 1 } " ou " { 0 , 3 } ". Le but est de diriger les bords du graphe de sorte que le degré extérieur de chaque sommet soit dans l'ensemble étiquetant ce sommet.{1}{0,3}

La réduction doit prendre en entrée une instance d'orientation graphique et produire une liste de triplets en sortie. Dans cette réduction, les triplets que nous produisons satisferont toujours certaines contraintes. Ces contraintes sont répertoriées ci-dessous, et nous ferons référence à une liste de triplets comme valides si et seulement s'ils satisfont à ces contraintes:

  • Les caractères x , y et c ne reçoivent que des intervalles contenant exactement un index. En d'autres termes, chaque fois que ces personnages sont placés, ils sont placés dans des emplacements spécifiques.xyc
  • Pour chaque triple ( i , l , r ) présent dans l'instance avec i { 0 ,(i,l,r) 1 } , le triple ( 1 - i , l , r ) est également présent.i{0,1}(1i,l,r)
  • Si ( α , l , r ) et ( α , l , r ) sont tous les deux des triplets présents dans l'instance, alors soit l < l r < r , soit l < l r < r , soit { α , α } = { 0 , 1 } avec l = l(α,l,r)(α,l,r)l<lr<rl<lr<r{α,α}={0,1} < R = r .l=l<r=r
  • Si ( α , l , r ) est un triple alors le nombre de triplets ( α , l , r ) avec l l r r est exactement r - l + 1 .(α,l,r)(α,l,r)llrrrl+1

Notez le lemme suivant, prouvé à la fin de ce post.

Lemme: pour une liste valide de triplets, les caractères x , y et c doivent être placés exactement comme indiqué par les triplets, et pour toute paire de triplets ( 0 , l , r ) et ( 1 , l , r ) , le deux caractères pour ce triple doivent être placés aux indices l et r .xyc(0,l,r)(1,l,r)lr

L'idée de la réduction est alors la suivante.

Nous utilisons des paires de triplets ( 0 , l , r ) et ( 1 , l , r ) pour représenter les arêtes. Le bord va entre les points d'extrémité à l'indice l et à l'indice r . En supposant que nous produisions une liste valide de triplets, les caractères de ces deux triplets doivent être placés à l et r , afin que nous puissions traiter l'ordre dans lequel ils sont placés comme indiquant la direction du bord. Ici 1 est la "tête" du bord et 0 est la "queue". En d'autres termes, si le 1 est placé à r(0,l,r)(1,l,r)lrlr101ralors le bord pointe de l à r et si le 1 est placé à l alors le bord pointe de r à l .lr1lrl

Pour représenter les sommets, nous plaçons un caractère x ou y à un index et utilisons les trois caractères suivants comme extrémités des trois arêtes qui touchent le sommet. Notez que si l' on place un x , les trois arêtes au sommet doivent pointer dans la même direction (tous dans le sommet ou tous du sommet) simplement en raison des chaînes qui sont dans un langage fini A . Ces sommets ont un degré 0 ou 3 , nous plaçons donc un x exactement pour les sommets étiquetés { 0 , 3 } . Si nous plaçons un yxyxA03x{0,3}y, exactly one of the three edges at the vertex must point in the same direction due to the strings in AA. Such vertices have outdegree 11, so we place a yy exactly for the vertices labeled {1}{1}.

In some sense, we are done. In particular, the correspondence between solving this instance and solving the Graph Orientation instance should be clear. Unfortunately, the list of triples we produce may not be valid, and so the "edges" described may not work as intended. In particular, the list of triples might not be valid because the condition that the intervals from the triples must always contain each other might not hold: the intervals from two edges may overlap without one containing the other.

Pour lutter contre cela, nous ajoutons quelques infrastructures supplémentaires. En particulier, nous ajoutons des "sommets croisés". Un sommet croisé est un sommet de degré 4 dont les bords sont appariés de telle sorte que dans chaque paire, un bord doit pointer vers le sommet croisé et un vers l'extérieur. En d'autres termes, un sommet croisé se comportera de la même manière que deux arêtes "croisées". Nous représentons un sommet croisé en plaçant le caractère c à un certain indice i . Notez ensuite que le langage A contraint les caractères en i - 1 et i + 2 à être opposés (un 0 et un 1 ) et les caractères en i - 24ciAi1i+201i2et i + 1 pour être opposé. Ainsi, si nous utilisons ces indices comme points de terminaison pour les quatre arêtes au sommet du croisement, le comportement est exactement comme décrit: les quatre arêtes sont par paires et parmi chaque paire, un point d'entrée et un point de sortie.i+1

How do we actually place these crossovers? Well suppose we have two intervals (l,r)(l,r) and (l,r)(l,r) which overlap. WLOG, l<l<r<rl<l<r<r. We add the crossover character into the middle (between ll and rr). (Let's say that all along we spaced everything out so far that there's always enough space, and at the end we will remove any unused space.) Let the index of the crossover character be ii. Then we replace the four triples (0,l,r)(0,l,r), (1,l,r)(1,l,r), (0,l,r)(0,l,r), and (1,l,r)(1,l,r) with eight triples with two each (one with character 00 and one with character 11) for the following four intervals (l,i1)(l,i1), (i+2,r)(i+2,r), (l,i2)(l,i2), (i+1,r)(i+1,r). Notice that the intervals don't overlap in the bad way anymore! (After this change, if two intervals overlap, one is strictly inside the other.) Furthermore, the edge from ll to rr is replaced by an edge from ll to the crossover vertex followed by the edge from there to rr; these two edges are paired at the crossover vertex in such a way that one is pointed in and one is pointed out; in other words, the two edges together behave just like the one edge they are replacing.

In some sense, putting in this crossover vertex "uncrossed" two edges (whose intervals were overlapping). It is easy to see that adding the crossover vertex can't cause any additional edges to become crossed. Thus, we can uncross every pair of crossing edges by inserting enough crossover vertices. The end result still corresponds to the Graph Orientation instance, but now the list of triples is valid (the properties are all easy to verify now that we have "uncrossed" any crossing edges), so the lemma applies, the edges must behave as described, and the correspondence is actually an equivalence. In other words, this reduction is correct.


proof of lemma

Lemma: for a valid list of triples, the characters xx, yy, and cc must be placed exactly as indicated by the triples, and for any pair of triples (0,l,r)(0,l,r) and (1,l,r)(1,l,r), the two characters for that triple must be placed at indices ll and rr.

proof:

We proceed by induction on the triples by interval length. In particular, our statement is the following: for any kk if some triple has interval length kk then the character in that triple must be placed as described in the lemma.

Base case: for k=0k=0, the triple must be placing a character xx, yy, or cc at the single index inside the interval. This is exactly as described in the lemma.

Inductive case: assume the statement holds for any kk less than some kk. Now consider some triple with interval length kk. Then that triple must be of the form (i,l,r)(i,l,r) with r=l+k1r=l+k1 and i{0,1}i{0,1}. The triple (1i,l,r)(1i,l,r) must also be present. The number of triples (α,l,r)(α,l,r) with llrrllrr is exactly rl+1=krl+1=k. These triples include triples (0,l,r)(0,l,r) and (1,l,r)(1,l,r) but also k2k2 other triples of the form (α,l,r)(α,l,r) with l<lr<rl<lr<r. These other triples all have interval length smaller than kk, so they all must place their characters as specified in the lemma. The only way for this to occur is if these triples place characters in every index starting at index l+1l+1 and ending at index r+1r+1. Thus, our two triples (0,l,r)(0,l,r) and (1,l,r)(1,l,r) must place their characters at indices ll and rr, as described in the lemma, concluding the inductive case.

By induction, the lemma is correct.

Mikhail Rudoy
la source
Thanks a lot for this elaborate proof, and with a very simple language! I think it is correct, the only thing I'm not sure about is the claim that "adding the crossover vertex can't cause any additional edges to become crossed". Couldn't it be the case that the interval (l,r)(l,r) included some other interval (l,r)(l′′,r′′) with llrrll′′r′′r, and now one of (l,i1)(l,i1) and (i+2,r)(i+2,r) crosses it? It seems like the process still has to converge because the intervals get smaller, but that's not completely clear either because of the insertion of crossover vertices. How should I see it?
a3nm
If l<l<r<rl<l<r<r, then you can insert the new indices for the new crossover vertex immediately to the right of ll. This causes the new indices (i±i± a bit) to be in exactly those intervals that used to contain ll. It should be easy to see that adding a crossover vertex can add a new crossing with some other interval only if the new indices fall in the other interval. If l<l<r<rl<l′′<r′′<r then the new indices do not fall into the interval (l,r)(l′′,r′′). If l<l<r<rl<l′′<r′′<r then the new indices might fall into the interval (l,r)(l′′,r′′), but only if ll already fell into that
Mikhail Rudoy
(continued) interval. In this case, you aren't actually creating a new crossing, just turning an old crossing with the old interval (l,r)(l,r) into a new crossing with the interval (i+something,r)(i+something,r)
Mikhail Rudoy
I guess in your second message you meant "with the old interval (l,r)(l,r)" rather than "(l,r)(l,r)"? But OK, I see it: when you add the crossing vertex, the only bad case would be an interval II that overlap with a new interval without overlapping with the corresponding interval. This cannot happen for supersets of (l,r)(l,r) or of (l,r)(l,r): if they overlap with a new interval then they overlapped with the old one. Likewise for subsets of (l,r)(l,r) or (l,r)(l,r) for the reason that you explain. So I agree that this proof looks correct to me. Thanks again!
a3nm
2

@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 LL that we use is more complicated.

The key to show hardness is to design a language LL that allows us to guess a word and repeat it multiple times. Specifically, for any number kk of variables and number mm of clauses, we will build intervals that ensure that all words ww of LL that we can form must start with an arbitrary word uu of length kk on alphabet {0,1}{0,1} (intuitively encoding a guess of the valuation of variables), and then this word uu is repeated mm 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}A={0,1,#,0,1} and the language: L:=(0|1)(#(00|11))#(0|1)L:=(0|1)(#(00|11))#(0|1). The formal claim is a bit more complicated:

Claim: For any numbers k,mNk,mN, we can build in PTIME a set of intervals such that the words in LL that can be formed with these intervals are precisely:

{u(#(˜u˜u)#(uu))m#˜uu{0,1}k}

{u(#(u~u~)#(uu))m#u~u{0,1}k}

where ˜uu~ denotes the result of reversing the order of uu and swapping 00's and 11's, where uu denotes the result of adding a prime to all letters in uu, and where xyxy for two words xx of yy of length pp is the word of length 2p2p formed by taking alternatively one letter from xx and one letter from yy.

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

choice gadget

It's easy to show the following observation (ignoring LL for now): the possible words that we can form with these intervals are exactly u#˜uu#u~ for u{0,1}ku{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 00 and one 11, etc.

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

duplication gadget

For now take L:=(0|1)(#(00|11))#(0|1)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, LL 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#(˜u˜u)#uu#(u~u~)#u for u{0,1}ku{0,1}k.

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

duplication gadget, repeated

As before, we could show (by induction on mm) that the possible words are exactly the following: u(#˜u˜u#uu)2#˜uu(#u~u~#uu)2#u~ for u{0,1}ku{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 uu. 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 ww of length nn, and we ask whether the intervals can form a word uu such that wuwu is in LL.) 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:

unit annotations

Thanks to this observation, to check clauses, we will define our regular language LL to be the intersection of two languages. The first language enforces that the sub-word on even positions is a word in LL, i.e., if we ignore the annotations then the word must be in LL, so we can just use the construction of the claim and add some annotations. The second language LL′′ will check that the clauses are satisfied. To do this, we will add three letters in our alphabet, to be used as annotations: ++, , and ϵ. At clause 1im, 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~ϵ. 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.

a3nm
la source