Apakah teka-teki silang regex NP-keras?

Saya bermain-main beberapa hari lalu di situs web ini: http://regexcrossword.com/ dan itu membuat saya bertanya-tanya apa cara terbaik untuk menyelesaikannya.

Bisakah Anda memecahkan masalah berikut dalam waktu polinomial atau NP-keras?

Diberi kisi NxM dengan N ekspresi reguler untuk kolom dan M untuk baris, temukan solusi apa pun untuk kisi sehingga semua ekspresi reguler terpenuhi, atau katakan bahwa tidak ada solusi.

Masalahnya adalah NP-hard.

Kami menunjukkan ini dengan mengurangi penutup simpul:

Diberikan grafik dan ambang k , apakah ada subset V ′ ⊆ V kardinalitas paling banyak k , sehingga setiap sisi dalam E adalah insiden setidaknya satu simpul dalam V ′ ?$G=(V,E)$$k$$V' \subseteq V$$k$$E$$V'$

Kami menerjemahkan ini menjadi teka-teki silang regex dengan kolom dan | V | baris sebagai berikut:$|E|+1$$|V|$

Semua kolom, kecuali yang pertama, berhubungan dengan tepi. Mereka mendapatkan regex .$0^*1(0|1)^*$

Semua baris berhubungan dengan suatu titik. Mereka mendapatkan regex yang memungkinkan untuk menulis

• a di kolom pertama dan setiap kolom yang terkait dengan insiden tepi ke simpul itu dan nol di semua kolom lainnya, atau$1$

• $0^*$

Akhirnya, kolom pertama menghitung ukuran penutup simpul. Ia mendapat regex, yang memungkinkan paling banyak yang .$k$

Korespondensi antara solusi untuk teka-teki silang regex dan penutup vertex harus jelas.

Contoh:

Temukan penutup vertex ukuran 2 untuk grafik berikut:

$V_A = 0^* \big| 10110$

$V_B = 0^* \big| 11101$

$V_C = 0^* \big| 10011$

$V_D = 0^* \big| 11000$

$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$

$E_1 = 0^*1(0|1)^*$

$E_2 = 0^*1(0|1)^*$

$E_3 = 0^*1(0|1)^*$

$E_4 = 0^*1(0|1)^*$

Terakhir, Anda dapat mengatur "silang" sehingga melalui V D adalah atas regexes dan C o $V_A$$V_D$$Counter$$E_1$$E_4$

Memecahkan teka-teki silang regex ini memberi Anda penutup titik ukuran 2 untuk simpul $V_A,V_B$$V_C,V_B$

Jika kita mengubah k menjadi 1 dan menjadi$Counter$$0^* \big| 0^*10^*$

Pertanyaannya tetap lengkap NP bahkan ketika semua ekspresi reguler sama. http://arxiv.org/abs/1411.5437