Является ли regex golf NP-Complete?

27

Как видно в этой недавней полосе XKCD и в этом недавнем сообщении в блогеПо словам Питера Норвига (история Слэшдота, в которой рассказывается о последнем), «регулярное выражение в гольфе» (которое лучше назвать проблемой разделения регулярных выражений) - это задача определения кратчайшего из возможных регулярных выражений, которое принимает каждое слово в множестве А, а слово в сет Б. Норвиг включает в себя алгоритм генерации достаточно короткого кандидата, и он отмечает, что его подход предполагает решение NP-полной задачи «Обложка множества», но он также осторожно указывает, что его подход не учитывает все возможные регулярные выражения, и, конечно, его алгоритм не обязательно является единственным, поэтому его решения не гарантируют оптимальности, а также возможно, что какой-то другой алгоритм с полиномиальным временем может найти эквивалентные или лучшие решения.

Для конкретности и во избежание необходимости решать вопрос оптимизации, я думаю, наиболее естественной формулировкой разделения регулярных выражений будет:

Для двух (конечных) наборов строк и B в некотором алфавите Σ существует ли регулярное выражение длины k, которое принимает каждую строку в A и отклоняет каждую строку в B ?ABΣkAB

Что-нибудь известно о сложности этой конкретной проблемы разделения? (Обратите внимание, что, поскольку я указал и B как конечные наборы строк, естественным понятием размера для задачи является общая длина всех строк в A и B ; это перекрывает любой вклад от k ). Мне кажется весьма вероятным, что он является NP-завершенным (и на самом деле, я бы ожидал, что сокращение будет связано с какой-то проблемой прикрытия), но некоторые поиски не нашли ничего особенно полезного.ABABk

Стивен Стадницки
источник
4
Это даже в НП? Учитывая регулярное выражение, как вы проверяете, есть ли слово в описанном языке за полиномиальное время? Стандартный подход - преобразование в NFA, затем DFA и проверка - занимает экспоненциальное время в (?). k
Рафаэль
1
должен быть PSPACE-полным; см. (Gramlich, Schnitger, Минимизация NFA и регулярных выражений, 2005) по адресу ggramlich.github.io/Publications/approximationSTACS05Pres.pdf и citeseerx.ist.psu.edu/viewdoc/… (PS: я публикую это как комментарий, потому что ответ должен объяснить, почему, но у меня нет времени, чтобы сделать это в данный момент, возможно, кто-то другой может использовать ссылку и объяснить, как она работает)
rgrig
1
Для регулярных выражений, как это понимается в TCS, проблема заключается в NP (сертификатом полиномиального размера, который можно проверить за полиномиальное время, будет само регулярное выражение). Это (вероятно) не в NP, если мы используем, например, PCRE для регулярных выражений, потому что даже тестирование членства является NP-сложным ( perl.plover.com/NPC/NPC-3SAT.html ).
Майк Б.
1
@MikeB .: А как именно вы проверяете за полиномиальное время? Вы видели комментарий @Raphael?
rgrig
5
(1) Вы можете запустить детерминистический алгоритм в P, чтобы проверить членство NFA (начните с начального состояния и запомните все состояния, в которых вы можете находиться после употребления символа слова. Достигните конца, проверьте, достигли ли вы хотя бы одно конечное состояние.) (2) Это зависит от определения «регулярного выражения» - используем ли мы одного из программистов или программистов? Разрешаем ли мы только обычные языки или (подмножество) контекстно-зависимых языков (следовательно, PCRE)?
Майк Б.

Ответы:

15

Предполагая TCS-вариант регулярного выражения, проблема действительно является NP-полной.

Мы предполагаем, что наши регулярные выражения содержат

  • буквы из , совпадающие между собой,Σ
  • , обозначающий союз,+
  • , обозначая конкатенацию,
  • , обозначая Клини-Стар,
  • , соответствующий пустой строкеλ

и ничего больше. Длина регулярного выражения определяется как количество символов из . Как и в комиксе, мы считаем, что регулярное выражение соответствует слову, если оно соответствует подстроке слова. (Изменение любого из этих предположений должно влиять только на сложность конструкции ниже, но не на общий результат.)Σ

То, что он находится в NP, является простым, как объяснено в комментариях (проверьте кандидата-RE, переведя его в NFA и выполнив это для всех слов из и B ).AB

Чтобы показать NP-твердость, мы уменьшаем покрытие набора:

При заданном юниверсе и наборе C подмножеств U , существует ли множество C C размераUCUCC чтобыS C S = U ?kSCS=U

Мы переводим вход для Set set в один для regex golf следующим образом:

  • содержит один символ для каждого подмножества в C и один дополнительный символ (в дальнейшем обозначается x ).ΣCx
  • Содержит одно слово для каждого элемента е из U . Слово состоит точно из символов, представляющих подмножества в C, которые содержат e (в произвольном порядке).AeUCe
  • содержит одно слово x .Bx
  • просто переносится.k

Это сокращение очевидно в P, и эквивалентность также довольно проста:

  • Если c1,,ck является решением для заданного экземпляра покрытия, регулярное выражение является решением для регулярного выражения golf.c1++ck
  • Регулярное выражение, соответствующее пустому подслову, будет соответствовать . Таким образом, любое регулярное выражение решения задачи гольф должен содержать по крайней мере одну букву от каждого из слов в A . Следовательно, если экземпляр гольфа разрешим, существует множество не более k букв из ΣxAkΣ так что каждое слово в покрывается этим набором букв. По построению соответствующий набор подмножеств из C является решением для экземпляра set cover.AC
FrankW
источник
1
Очень хорошо, позвольте мне добавить 2 пункта, для полноты: (1) В качестве дополнительного предположения относительно спецификации проблемы, и B должны быть конечными множествами (и все элементы перечисляются явно?) (2) Размер RE-кандидата находится в O ( n ) , так как a 1 + a 2 + . , , , a iA является действительным кандидатом с размером в O ( n ) , поэтому для каждого большего k ответ тривиально верен. ABO(n)a1+a2+,,,,aяAО(N)К
Майк Б.
2
@Mike B .: (1): конечность и B дана в вопросе. В теории сложности исчерпывающий листинг является стандартным способом представления конечных множеств. (2) действительно обязательный аргумент, если кто-то хочет сделать строгую часть «в NP». AВ
FrankW