Проверка того, можно ли запланировать буквы для достижения слова на обычном языке

23

Я фиксируем регулярный язык на алфавите , и я считаю следующую проблему , которую я называю письмо планирования для L . Неофициально, ввод дает мне n букв и интервал для каждой буквы (то есть минимальную и максимальную позицию), и моя цель состоит в том, чтобы поместить каждую букву в ее интервал так, чтобы никакие две буквы не были сопоставлены одной и той же позиции и чтобы в результате чего п -Письма слова в L . Формально:L LΣΣL Ln nn nLL

  • Ввод: Nn троек ( a i , l i , r i )(ai,li,ri) где a iΣaiΣ и 1 l ir in1lirin - целые числа
  • Вывод: есть ли биекция f : { 1 , , n } { 1 , , n }f:{1,,n}{1,,n} такая, что l if ( i ) r ilif(i)ri для всех яi и a f - 1 ( 1 )a f - 1 ( n )Laf1(1)af1(n)L .

Очевидно, что эта проблема в NP, путем угадывания биекции еf и проверки принадлежности к LL в PTIME. Мой вопрос: существует ли такой обычный язык LL , что задача планирования букв для LL является NP-сложной?

Некоторые начальные наблюдения:

  • Похоже, что аналогичные проблемы были изучены при планировании: мы могли рассматривать проблему как планирование задач с удельной стоимостью на одной машине при соблюдении дат начала и окончания. Тем не менее, эта последняя проблема явно в PTIME с жадным подходом, и я не вижу ничего в литературе по планированию для случая, когда задачи помечены, и мы хотели бы получить слово на целевом регулярном языке.
  • Другой способ увидеть проблему является как частный случай двудольного задачи максимального соответствия (между буквами и позицией), но опять - таки это трудно выразить ограничение , что мы должны упасть в LL .
  • В конкретном случае, когда LL является языком формы ты u для некоторого фиксированного слова Uu (например, ( а б ) (ab) ), тогда задача планирования букв для LL находится в PTIME с простым жадным алгоритмом: построить слово из слева направо и поместите в каждой позиции одну из доступных букв, которая является правильной относительно LL и имеет наименьшее время г яri . (Если нет доступных букв, которые являются правильными, произойдет сбой.) Однако это не распространяется на произвольные обычные языки LL потому что для таких языков у нас может быть выбор, какой тип буквы использовать.
  • Похоже, динамический алгоритм должен работать, но на самом деле это не так просто: кажется, вам нужно запомнить, какой набор букв вы уже взяли. Действительно, при построении слова слева направо, когда вы достигли позиции яi , ваше состояние зависит от того, какие буквы вы употребили до сих пор. Вы не можете запомнить весь набор, потому что тогда будет экспоненциально много состояний. Но это не так просто «суммировать» (например, сколько копий каждой буквы было использовано), потому что, чтобы узнать, какие копии вы использовали, кажется, что вам нужно помнить, когда вы их использовали (чем позже вы потребляли) их, тем больше писем было в наличии). Даже с таким языком, как ( a b | b a ) (ab|ba) ,а бab и когда вы должны принять б аba зависимости от того, какие буквы вам понадобятся позже и когда они станут доступны.
  • Однако, поскольку обычный язык LL является фиксированным и не может запоминать так много информации, мне трудно найти NP-сложную проблему, которую я мог бы уменьшить.
a3nm
источник
Можете ли вы получить NP-полноту для некоторого L в PTIME?
Лэнс Фортноу,
3
@LanceFortnow Конечно. Вы можете дополнить 3CNF так, чтобы каждая переменная встречалась в четном количестве литералов, и каждые два последовательных вхождения отменялись. Кодируйте в или , затем в экземпляре календарного планирования символы фиксируются, а остальные равны половине и половине . За полиномиальное время можно проверить, кодирует ли строка заполненный 3CNF, который оценивается как true. x i 0 i 1 i ( , ) , , 0 1xi0i1i(,),,01
Уиллард Жан
Вы также можете обобщить задачу на «произвольные позиции» (не ограничиваясь 1..n). Возможно, легче доказать твердость (если это трудно).
Марцио Де
@MarzioDeBiasi: Я не уверен, что понимаю, ты имеешь в виду, что положение букв может быть любым произвольным подмножеством, а не интервалом? Я не знаю, сложно ли это (это начинает немного напоминать проблему точного точного соответствия ), но версия с интервалами допускает жадный алгоритм, когда поэтому я надеюсь, что это может быть проще. L = u L =u*
3
@ a3nm: нет, я имею в виду, что вы можете обобщить снятие ограничения ; вы просите слово в L, в котором есть хотя бы одна буква в диапазоне ; другими словами, вы не «строите» полное слово длины , а запрашиваете слово произвольной длины, которое содержит заданные буквы в допустимых диапазонах. Я не знаю, меняет ли это сложность проблемы, но в этом случае вы должны столкнуться с «индексами», которые, возможно, не ограничены полиномиально длиной входных данных. r in a i [ l i . , r i ] nряnaя[lя, ,rя]N
Марцио Де Биаси

Ответы:

7

Задача NP-трудна для где - конечный язык, содержащий следующие слова:L=AL = A*AA

  • х 111 х 000х 111 , ,х 000
  • у 100 , у 010 , у 001 ,Y100Y010Y001
  • 00 c 11 , 01 c 10 , 10 c 01 и 11 c 0000 с 1101 с 1010c0111c00

Сокращение связано с проблемой Ориентация графика, которая, как известно, является NP-трудной (см. Https://link.springer.com/article/10.1007/s00454-017-9884-9 ). В этой задаче нам дан 3-регулярный неориентированный граф, в котором каждая вершина помечена либо " { 1 } ", либо " { 0 , 3 } ". Цель состоит в том, чтобы направить ребра графа таким образом, чтобы конечная точка каждой вершины находилась в наборе, обозначающем эту вершину.{1}{0,3}

Сокращение должно принимать в качестве входных данных экземпляр Graph Orientation и выводить список троек в качестве выходных данных. В этом сокращении тройки, которые мы выводим, всегда будут удовлетворять определенным ограничениям. Эти ограничения перечислены ниже, и мы будем ссылаться на список троек как действительный, если и только если они удовлетворяют этим ограничениям:

  • Символам x , y и c задаются только интервалы, содержащие ровно один индекс. Другими словами, всякий раз, когда эти символы размещаются, они размещаются в определенных местах.xyc
  • Для каждой тройки ( i , l , r ), присутствующей в случае с i { 0 , 1 } , тройка ( 1 - i , l , r ) также присутствует.(i,l,r)i{0,1}(1i,l,r)
  • Если ( α , l , r ) и ( α , l , r ) являются тройками, присутствующими в данном случае, то либо l < l r < r , либо l < l r < r , либо { α , α } = { 0 , 1 } с l = l(α,l,r)(α,l,r)l<lr<rl<lr<r{α,α}={0,1} < R = r .l=l<r=r
  • Если ( α , л , г ) является тройной , то число троек ( α ' , л ' , г ' ) с л L 'R 'г ровно г - л + 1 .(α,l,r)(α,l,r)llrrrl+1

Обратите внимание на следующую лемму, доказанную в конце этого поста.

Лемму: для действительного списка троек, символы х , у , и с должны быть помещены точно так , как указано троек, и для любой пары троек ( 0 , л , г ) и ( 1 , л , г ) , то два символа для этой тройки должны быть помещены в индексы l и r .xyc(0,l,r)(1,l,r)lr

Тогда идея сокращения заключается в следующем.

Мы используем пары троек ( 0 , l , r ) и ( 1 , l , r ) для представления ребер. Ребро проходит между конечными точками по индексу l и по индексу r . Предполагая, что мы создаем действительный список троек, символы из этих двух троек должны быть размещены в l и r , поэтому мы можем рассматривать порядок, в котором они располагаются, как указание направления края. Здесь 1 - «голова» края, а 0 - «хвост». Другими словами, если 1 находится в т(0,l,r)(1,l,r)lrlr101rтогда край указывает от l до r, и если 1 помещен в l, то край указывает от r до l .lr1lrl

Чтобы представить вершины, мы помещаем символ x или y в индекс и используем следующие три символа в качестве конечных точек трех ребер, которые касаются вершины. Обратите внимание , что если мы размещаем х , все три ребра на вершине должны указывать в том же направлении (все в вершину или все из вершины) просто из строк, которые в конечном языке A . Такие вершины имеют степень 0 или 3 , поэтому мы ставим x точно для вершин, помеченных { 0 , 3 } . Если мы разместим уxyxA03x{0,3}y, Ровно один из трех ребер в вершине должны указывать в том же направлении , из - за строки в A . Такие вершины имеют степень 1 , поэтому мы ставим y точно для вершин, помеченных { 1 } .A1y{1}

В некотором смысле, мы сделали. В частности, должно быть ясно соответствие между решением этого экземпляра и решением экземпляра Graph Orientation. К сожалению, список производимых нами троек может оказаться недействительным, поэтому описанные «ребра» могут работать не так, как задумано. В частности, список троек может быть недействительным, поскольку условие, что интервалы из троек должны всегда содержать друг друга, может не соблюдаться: интервалы от двух ребер могут перекрываться, если один из них не содержит другой.

Чтобы бороться с этим, мы добавим еще немного инфраструктуры. В частности, мы добавляем «вершины кроссовера». Пересекающаяся вершина - это вершина степени 4 , ребра которой спарены так, что в каждой паре одно ребро должно указывать на вершину пересечения, а другое - наружу. Другими словами, пересеченная вершина будет вести себя так же, как и два «пересекающихся» ребра. Мы представляем пересеченную вершину, помещая символ c в некоторый индекс i . Затем обратите внимание, что язык A ограничивает символы в i - 1 и i + 2 противоположными (один 0 и один 1 ) и символы в i - 24ciAi1i+201i2и я + 1, чтобы быть противоположным. Таким образом, если мы используем эти индексы в качестве конечных точек для четырех ребер в вершине кроссовера, поведение будет точно таким, как описано: четыре ребра попарно попарно, и среди каждой пары один указывает и один указывает.i+1

Как мы на самом деле размещаем эти кроссоверы? Хорошо, предположим, у нас есть два интервала ( l , r ) и ( l , r ), которые перекрываются. WLOG, l < l < r < r . Мы добавляем символ пересечения в середину (между l и r ). (Допустим, что все это время мы разбрасывали все так, чтобы всегда было достаточно места, и в конце мы удалим все неиспользуемые места.) Пусть индекс символа кроссовера будет i . Затем мы заменим четыре тройки ( 0(l,r)(l,r)l<l<r<rlri, l , r ) , ( 1 , l , r ) , ( 0 , l , r ) и ( 1 , l , r ) с восемью тройками по две каждая (одна с символом 0 и одна с символом 1 ) для следующих четырех интервалов ( l , i - 1 ) , ( i + 2 , r )(0,l,r)(1,l,r)(0,l,r)(1,l,r)01(l,i1)(i+2,r), ( l , i - 2 ) , ( i + 1 , r ) . Обратите внимание, что интервалы больше не пересекаются в плохой форме! (После этого изменения, если два интервала перекрываются, один находится строго внутри другого.) Кроме того, ребро от l до r заменяется ребром от l до вершины кроссовера, за которым следует ребро оттуда до r ; эти два ребра спарены в вершине пересечения таким образом, что один направлен внутрь, а другой направлен; другими словами, два ребра вместе ведут себя так же, как один ребро, которое они заменяют.(l,i2)(i+1,r)lrlr

В некотором смысле, помещая в эту пересеченную вершину «некрещенные» два ребра (чьи интервалы перекрывались). Легко видеть, что добавление пересеченной вершины не может вызвать пересечение дополнительных ребер. Таким образом, мы можем пересечь каждую пару пересекающихся ребер, вставив достаточное количество пересеченных вершин. Конечный результат по-прежнему соответствует экземпляру Graph Orientation, но теперь список троек действителен (теперь все свойства легко проверить, когда мы «пересекаем» любые пересекающиеся ребра), поэтому применяется лемма, ребра должны вести себя как описано и соответствие на самом деле является эквивалентностью. Другими словами, это сокращение является правильным.


доказательство леммы

Лемму: для действительного списка троек, символы х , у , и с должны быть помещены точно так , как указано троек, и для любой пары троек ( 0 , л , г ) и ( 1 , л , г ) , то два символа для этой тройки должны быть помещены в индексы l и r .xyc(0,l,r)(1,l,r)lr

доказательство:

Поступаем по индукции на тройки по длине интервала. В частности, наше утверждение таково: для любого k, если некоторая тройка имеет длину интервала k, символ в этой тройке должен быть размещен, как описано в лемме.kk

Базовый случай: для k = 0 тройка должна помещать символ x , y или c в один индекс внутри интервала. Это именно так, как описано в лемме.k=0xyc

Индуктивный случай: предположим, что утверждение верно для любого k, меньшего некоторого k . Теперь рассмотрим некоторую тройку с длиной интервала k . Тогда эта тройка должна иметь вид ( i , l , r ) с r = l + k - 1 и i { 0 , 1 } . Тройка ( 1 - i , l , r ) также должна присутствовать. Количество троек ( αkkk(i,l,r)r=l+k1i{0,1}(1i,l,r) , L , r ) с l l r r в точности равно r - l + 1 = k . Эти тройки включают в себя тройки ( 0 , l , r ) и ( 1 , l , r ), а также k - 2 других тройки вида ( α , l (α,l,r)llrrrl+1=k(0,l,r)(1,l,r)k2, r ' ) с l < l r < r . Эти другие троек все имеют длину интервала меньшечем к ' , поэтому все они должны размещать свои символыкак указано в лемме. Единственный способ сделать это, если эти тройки размещают символы в каждом индексе, начиная с индекса l + 1 и заканчивая индексом r + 1 . Таким образом, наши две тройки ( 0 , l , r ) и ( 1 , l , r )(α,l,r)l<lr<rkl+1r+1(0,l,r)(1,l,r)должны поместить свои символы в индексы l и r , как описано в лемме, завершающей индуктивный случай.lr

По индукции лемма верна.

Михаил Рудой
источник
Большое спасибо за это сложное доказательство и с очень простым языком! Я думаю, что это правильно, единственное, в чем я не уверен, это утверждение, что «добавление пересеченной вершины не может привести к пересечению каких-либо дополнительных ребер». Не может ли быть так, что интервал ( l , r ) включал некоторый другой интервал ( l , r ) с l l r r , а теперь один из ( l , i - 1 ) и ( я + 2 ,(l,r)(l′′,r′′)ll′′r′′r(l,i1)г ) пересекает это? Кажется, что процесс все еще должен сходиться, потому что интервалы становятся меньше, но это также не совсем понятно из-за вставки пересеченных вершин. Как мне это увидеть? (i+2,r)
августа
Если l < l < r < r , то вы можете вставить новые индексы для новой вершины кроссовера непосредственно справа от l . Это приводит к тому, что новые индексы ( i ± немного) находятся именно в тех интервалах, которые раньше содержали l ' . Должно быть легко увидеть, что добавление пересеченной вершины может добавить новое пересечение с некоторым другим интервалом, только если новые индексы попадают в другой интервал. Если l < l < r < r ′, то новые индексы не попадают в интервал (l<l<r<rli±ll<l′′<r′′<rl , r ) . Если l < l < r < r, тогда новые индексы могут попадать в интервал ( l , r ) , но только если l уже впал в это(l′′,r′′)l<l′′<r′′<r(l′′,r′′)l
Михаил Рудой
(продолжение) интервал. В этом случае вы фактически не создаете новый перекресток, а просто превращаете старый перекресток со старым интервалом ( l , r ) в новый перекресток с интервалом ( i + что-то , r )(l,r)(i+something,r)
Михаил Рудой
Я предполагаю, что в вашем втором сообщении вы имели в виду «со старым интервалом ( l , r ) » вместо « ( l , r ) »? Но хорошо, я вижу это: когда вы добавляете пересекающуюся вершину, единственным плохим случаем будет интервал I, который перекрывается новым интервалом, не перекрывая соответствующий интервал. Это не может произойти для надмножеств ( l , r ) или ( l , r ) : если они перекрываются с новым интервалом, то они перекрываются со старым. Аналогично для подмножеств ( л(l,r)(l,r)I(l,r)(l,r), r ) или ( l , r ) по той причине, которую вы объясняете. Поэтому я согласен, что это доказательство выглядит для меня правильным. Еще раз спасибо! (l,r)(l,r)
a3nm
2

@MikhailRudoy был первым, кто показал NP-твердость, но у нас с Луи была другая идея, которую, я думал, я мог бы изложить здесь, поскольку она работает несколько иначе. Мы сводим непосредственно из CNF-SAT, проблему булевой выполнимости для CNF . В обмен на это, обычный язык L, который мы используем, является более сложным.L

Ключ к проявлению твердости заключается в разработке языка L ′, который позволяет нам угадывать слово и повторять его несколько раз. В частности, для любого числа k переменных и числа m предложений мы построим интервалы, обеспечивающие, чтобы все слова w из L , которые мы можем сформировать, начинались с произвольного слова u длины k в алфавите { 0 , 1 } (интуитивно кодирование предположения об оценке переменных), а затем это слово и повторяется мLkmwLuk{0,1}um времена (которые мы позже будем использовать для проверки того, что каждое условие удовлетворяется предполагаемой оценкой).

Для этого мы зафиксируем алфавит A = { 0 , 1 , # , 0 , 1 } и язык: L : = ( 0 | 1 ) ( # ( 00 | 11 ) ) # ( 0 | 1 ) . Формальное утверждение немного сложнее:A={0,1,#,0,1}L:=(0|1)(#(00|11))#(0|1)

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#˜u for u{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 wu 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:

unit annotations

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 ϵ. 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
источник