Czy regex golf NP-Complete?

Jak widać na ostatnim pasku XKCD i najnowszym poście na bloguwedług Petera Norviga (i opowiadania Slashdota z tym ostatnim) „regex golf” (który można by lepiej nazwać problemem separacji wyrażeń regularnych) jest zagadką polegającą na zdefiniowaniu najkrótszego możliwego wyrażenia regularnego, które akceptuje każde słowo w zestawie A i nie ma słowa w post B. zestaw Norviga zawiera algorytm generowania rozsądnie krótkiego kandydata, i zauważa, że ​​jego podejście polega na rozwiązaniu problemu NP-Complete Set Cover, ale ostrożnie zaznacza, że ​​jego podejście nie uwzględnia każdego możliwego wyrażenia regularnego, i oczywiście jego niekoniecznie jest jedynym algorytmem, więc nie ma gwarancji, że jego rozwiązania będą optymalne, a także możliwe, że jakiś inny algorytm z czasem wielomianowym znajdzie równoważne lub lepsze rozwiązania.

Ze względu na konkretność i aby uniknąć konieczności rozwiązywania problemu optymalizacji, najbardziej naturalnym sformułowaniem separacji wyrażeń regularnych byłoby:

Biorąc pod uwagę dwa (skończone) zestawy i B ciągów znaków nad pewnym alfabetem Σ , czy istnieje wyrażenie regularne o długości ≤ k, które akceptuje każdy ciąg A i odrzuca każdy ciąg B ?$A$$B$$\Sigma$$\leq k$$A$$B$

Czy coś wiadomo na temat złożoności tego konkretnego problemu separacji? (Zauważ, że skoro podałem i B jako skończone zestawy łańcuchów, naturalnym pojęciem rozmiaru problemu są całkowite długości wszystkich łańcuchów w A i B ; to pochłania jakikolwiek wkład z k ). Wydaje mi się bardzo prawdopodobne, że jest kompletny z NP (i faktycznie spodziewałbym się, że redukcja będzie miała jakiś problem z ochroną), ale kilka wyszukiwań nie przyniosło nic szczególnie przydatnego.$A$$B$$A$$B$$k$

Zakładając wariant wyrażenia regularnego TCS, problem jest rzeczywiście NP-zupełny.

Zakładamy, że nasze wyrażenia regularne zawierają

• litery od , pasujące do siebie,$\Sigma$
• , oznaczający związek,$+$
• , oznaczający konkatenację,$\cdot$
• , oznaczające Kleene-Star,$*$
• , pasujące do pustego ciągu$\lambda$

i nic więcej. Długość wyrażenia regularnego jest definiowana jako liczba znaków z . Podobnie jak w komiksie, za wyrażenie regularne uważamy wyrażenie regularne, jeśli pasuje ono do podłańcucha słowa. (Zmiana któregokolwiek z tych założeń powinna mieć wpływ tylko na złożoność konstrukcji poniżej, ale nie na ogólny wynik).$\Sigma$

To, że jest w NP, jest proste, jak wyjaśniono w komentarzach (zweryfikuj kandydata-RE, tłumacząc go na NFA i uruchamiając to na wszystkich słowach z i B ).$A$$B$

Aby pokazać twardość NP, zmniejszamy pokrycie zestawu:

Biorąc pod uwagę wszechświat i zbiór C podzbiorów U , czy istnieje zbiór C ′ ⊆ C o wielkości ≤ k, tak że ⋃ S ∈ C ′ S = U ?$U$$C$$U$$C' \subseteq C$$\leq k$$\bigcup_{S \in C'} S = U$

Tłumaczymy dane wejściowe dla pokrycia zestawu na jedno dla wyrażeń regularnych w następujący sposób:

• zawiera jeden znak dla każdego podzestawu w C i jeden dodatkowy znak (oznaczony x poniżej).$\Sigma$$C$$x$
• Zawiera jedno słowo dla każdego elementu e z U . Słowo składa się dokładnie z znaków reprezentujących podzbiory w C, które zawierają e (w dowolnej kolejności).$A$$e$$U$$C$$e$
• zawiera pojedyncze słowo x .$B$$x$
• jest po prostu przenoszone.$k$

To zmniejszenie jest oczywiście w P, a równoważność jest również dość łatwa do zauważenia:

• Jeśli jest rozwiązaniem dla zestawu instancji okładki, wyrażenie regularne c 1 + ⋯ + c $c_1, \ldots, c_k$$c_1 + \cdots + c_k$ jest rozwiązaniem do wyrażenia regularnego golf.
• $x$$A$$k$$\Sigma$$A$$C$