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

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

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

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

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

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

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

• буквы из , совпадающие между собой,$\Sigma$
• , обозначающий союз,$+$
• , обозначая конкатенацию,$\cdot$
• , обозначая Клини-Стар,$*$
• , соответствующий пустой строке$\lambda$

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

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

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

При заданном юниверсе и наборе C подмножеств U , существует ли множество C ′ ⊆ C размера$U$$C$$U$$C' \subseteq C$ чтобы ⋃ S ∈ C ′ S = U ?$\leq k$$\bigcup_{S \in C'} S = U$

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

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

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

• Если $c_1, \ldots, c_k$ является решением для заданного экземпляра покрытия, регулярное выражение является решением для регулярного выражения golf.$c_1 + \cdots + c_k$
• Регулярное выражение, соответствующее пустому подслову, будет соответствовать . Таким образом, любое регулярное выражение решения задачи гольф должен содержать по крайней мере одну букву от каждого из слов в A . Следовательно, если экземпляр гольфа разрешим, существует множество не более k букв из $x$$A$$k$$\Sigma$ так что каждое слово в покрывается этим набором букв. По построению соответствующий набор подмножеств из C является решением для экземпляра set cover.$A$$C$