Для фиксированного языка на каком-то алфавите , давайте рассмотрим следующую проблему, которую я называю -Интерлевинг :
- Вход: два слова
- Вывод: существует ли там перемежения из а также который в ,
Здесь чередование двух слов а также это слово что можно получить интуитивно, взяв буквы а также сохраняя их относительный порядок. Формально, это чередование а также если мы можем разделить его на две непересекающиеся подпоследовательности, одна из которых равна а другой, который равен , Например, «bheleloll» - это чередование «привет» и «звонок».
Какова сложность -Взаимодействие проблемы, в зависимости от языка ? В частности:
- Если регулярный, то мы можем решить задачу с помощью динамического алгоритма на двух строках, который показывает, что он находится в классе NL. Нелегко ли это для некоторых обычных языков? Однако для некоторых обычных языков проблема явно в L (детерминированное пространство журналов). Есть ли какая-то характеристика языков, для которых проблема в L?
- Если не регулярно, проблема все еще в NL, когда имеет полиномиальную онлайн детерминированную сложность пространства (см. здесь это понятие или мой предыдущий вопрос ). Однако это не распространяется, например, на все контекстно-свободные языки; тем не менее, некоторые другие (например, палиндромы) также могут быть показаны как NL (например, путем выполнения динамического алгоритма одновременно с начала и с конца). Есть ли контекстно-свободный язык, чей-перемежение проблемы NP-трудно?