Apakah Regex golf NP-Complete?

Seperti yang terlihat di strip XKCD terbaru ini dan posting blog terbaru inidari Peter Norvig (dan sebuah kisah Slashdot yang menampilkan yang terakhir), "golf regex" (yang mungkin lebih baik disebut masalah pemisahan ekspresi reguler) adalah teka-teki untuk menentukan ekspresi reguler sesingkat mungkin yang menerima setiap kata pada set A dan tidak ada kata dalam set B. Posting Norvig mencakup algoritma untuk menghasilkan kandidat yang cukup pendek, dan dia mencatat bahwa pendekatannya melibatkan penyelesaian masalah Set Cover NP-lengkap, tetapi dia juga berhati-hati untuk menunjukkan bahwa pendekatannya tidak mempertimbangkan setiap kemungkinan ekspresi reguler, dan tentu saja itu bukan satu-satunya algoritma, jadi solusinya tidak dijamin optimal, dan mungkin juga beberapa algoritma waktu polinomial lain dapat menemukan solusi yang setara atau lebih baik.

Demi kebenaran dan untuk menghindari harus menyelesaikan pertanyaan optimasi, saya pikir formulasi Pemisahan Ekspresi Reguler yang paling alami adalah:

Dengan dua (hingga) set dan string di atas beberapa alfabet , apakah ada ekspresi reguler panjang yang menerima setiap string dalam dan menolak setiap string dalam ?B Σ ≤ k A $A$$B$$\Sigma$$\leq k$$A$$B$

Adakah yang diketahui tentang kerumitan masalah pemisahan ini? (Perhatikan bahwa karena saya telah menetapkan dan sebagai set string terbatas, gagasan alami ukuran untuk masalah adalah panjang total semua string dalam dan ; ini meniadakan kontribusi dari ). Tampaknya sangat mungkin bagi saya bahwa ini adalah NP-lengkap (dan pada kenyataannya, saya akan berharap pengurangan menjadi semacam masalah penutup) tetapi beberapa pencarian belum menemukan sesuatu yang sangat berguna.B A B $A$$B$$A$$B$$k$

Dengan asumsi varian TCS-regex, masalahnya memang NP-complete.

Kami berasumsi bahwa regex kami mengandung

• surat dari , cocok dengan mereka sendiri,$\Sigma$
• $+$ , yang menunjukkan kesatuan,
• $\cdot$ , yang menunjukkan penggabungan,
• $*$ , yang menunjukkan Kleene-Star,
• $\lambda$ , cocok dengan string kosong

dan tidak ada lagi. Panjang regex didefinisikan sebagai jumlah karakter dari . Seperti di strip komik, kami menganggap regex cocok dengan kata, jika cocok dengan substring kata. (Mengubah salah satu dari asumsi-asumsi ini hanya akan mempengaruhi kompleksitas konstruksi di bawah ini, tetapi bukan hasil umum.)$\Sigma$

$A$$B$

Untuk menunjukkan kekerasan NP, kami mengurangi Set penutup:

$U$$C$$U$$C' \subseteq C$$\leq k$$\bigcup_{S \in C'} S = U$

Kami menerjemahkan input untuk Set cover menjadi satu untuk regex golf sebagai berikut:

• $\Sigma$$C$$x$
• $A$$e$$U$$C$$e$
• $B$$x$
• $k$

Pengurangan ini jelas dalam P dan kesetaraan juga cukup sederhana untuk dilihat:

• $c_1, \ldots, c_k$$c_1 + \cdots + c_k$
• $x$$A$$k$$\Sigma$$A$$C$