Pengurangan polinom dari masalah NP-lengkap untuk PCP terbatas

Buku-buku teks di mana-mana mengasumsikan bahwa Masalah Korespondensi Bounded Post adalah NP-complete (tidak lebih dari $N$ indeks diizinkan dengan pengulangan). Namun, tidak ada satupun yang menunjukkan pengurangan polinomial waktu yang sederhana (seperti pada, sesuatu yang dapat dipahami oleh seorang mahasiswa sarjana) dari masalah NP-complete lainnya.

Namun setiap pengurangan yang dapat saya pikirkan adalah eksponensial (dengan $N$ atau dengan ukuran seri) dalam run-time. Mungkin dapat ditunjukkan bahwa itu dapat direduksi menjadi SAT?

Seperti yang sering terjadi dengan pengurangan NP, masuk akal untuk mencari masalah yang sama . Secara khusus, sulit untuk menyandikan kondisi global seperti "telah melihat beberapa node" ke PCP (dengan banyak polinomi) yang merupakan kontraindikasi masalah grafik, masalah pengepakan akan mengharuskan kita untuk menyandikan angka unary di PCP (membuat instance secara eksponensial besar), dan begitu seterusnya. Oleh karena itu, masalah string dengan hanya pembatasan lokal dapat diharapkan berfungsi dengan baik.

Pertimbangkan versi keputusan dari masalah supersequensi umum terpendek :

Diberikan dua string dengan | a | = n dan | b | = m dan k ∈ N , tentukan apakah ada string c ∈ Σ + dengan | c | ≤ k sehingga a dan b adalah c .$a,b \in \Sigma^+$$|a|=n$$|b|=m$$k \in \mathbb{N}$$c \in \Sigma^+$$|c| \leq k$$a$$b$$c$

Idenya adalah untuk membiarkan PCP membangun supersequences dan b dari kiri ke kanan, mengkodekan tumpang tindih ubin 'di mana posisi kita berada di a dan b , masing-masing. Ini akan menggunakan satu ubin per simbol dalam c , jadi k sesuai dengan batas BPCP: jika kita dapat menyelesaikan PCP ini dengan ubin ≤ k , Anda dapat membaca supersekuensinya dengan panjang yang sama, dan sebaliknya.$a$$b$$a$$b$$c$$k$$\leq k$

Konstruksi ubin agak membosankan, tetapi cukup jelas. Perhatikan bahwa kami tidak akan membuat petak yang tidak meneruskan atau b ; seperti itu tidak pernah bisa menjadi bagian dari supersequence umum terpendek , sehingga mereka berlebihan. Mereka dapat dengan mudah ditambahkan tanpa merusak sifat reduksi.$a$$b$

Angka-angka dalam tumpang tindih dikodekan dalam biner, tetapi menggunakan simbol di luar dan padding ke panjang log maks yang sama ( m , n ) . Dengan demikian kami memastikan bahwa ubin digunakan seperti yang disarankan oleh grafis (tetris), yaitu karakter dan tumpang tindih pengindeksan indeks tidak bercampur (PCP tidak mencegah hal ini per se). Kita butuh:$\Sigma$$\log \max(m,n)$

• Mulai ubin: dapat memulai dengan sebuah 1 , b 1 atau keduanya jika mereka sama.$c$$a_1$$b_1$
• Ubin perantara: dapat melanjutkan dengan simbol berikutnya dalam a , dalam b atau keduanya jika keduanya sama.$c$$a$$b$
• Mengakhiri ubin: berakhir dengan simbol terakhir dari a (jika yang terakhir dari b sudah terlihat), mirip dengan b , atau dengan simbol terakhir dari keduanya.$c$$a$$b$$b$

Ini adalah skema ubin. Perhatikan bahwa ubin perantara harus dipakai untuk semua pasangan . Seperti disebutkan di atas, buat ubin tanpa ∗ hanya jika masing-masing karakter dalam a dan b cocok.$(i,j) \in [n]\times [m]$$*$$a$$b$

^{[ sumber ]}

The adalah simbol untuk "tidak peduli"; pada ubin sebenarnya, simbol lain harus disalin di sana. Perhatikan bahwa jumlah ubin dalam Θ ( m n ) dan setiap ubin memiliki panjang 4 log maks ( m , n ) + 1 , sehingga instance BPCP yang dibuat (lebih dari alfabet Σ ∪ { 0 , 1 $*$$\Theta(mn)$$4\log \max(m,n) + 1$$\Sigma \cup \{0,1\}$plus simbol pemisahan) memiliki ukuran polinom. Lebih jauh, konstruksi setiap ubin jelas dimungkinkan dalam waktu polinomial. Oleh karena itu, pengurangan yang diusulkan memang merupakan transformasi polinomial yang valid yang mengurangi masalah supersequensi umum terpendek NP-lengkap menjadi BPCP.

Saya pikir Anda dapat membuktikan bahwa BPCP adalah NP-lengkap dengan menggunakan pengurangan yang sama dengan yang digunakan untuk membuktikan keraguannya. Kami akan langsung membuktikan bahwa BPCP adalah NP-lengkap dengan menunjukkan bagaimana mengurangi masalah dalam NP untuk itu dalam waktu polinomial.

Reduksi standar yang digunakan untuk membuktikan bahwa PCP tidak dapat ditentukan ( digambarkan di sini ) bekerja dengan membangun serangkaian ubin sehingga ada solusi PCP jika ada perhitungan penerimaan dari TM diberikan pada string w . Jumlah ubin yang dibuat dalam pengurangan ini secara polinomial besar - khususnya, jumlah domino yang dibangun adalah beberapa fungsi dari ukuran alfabet pita dan jumlah negara bagian dalam TM. Satu-satunya domino yang ukurannya mungkin besar adalah domino awal, yang memiliki $M$$w$$w$tertulis di atasnya. Jika kita menggeneralisasi pengurangan ini dari bekerja pada TM deterministik ke bekerja pada TM non-deterministik, maka ini paling banyak memperkenalkan sejumlah domino yang konstan, karena jumlah transisi terbatas. Sebagai konsekuensinya, kita dapat membuat set domino standar untuk pengurangan waktu tak terbatas normal dalam polinomial.

Mengingat hal ini, kita dapat mengurangi masalah NP menjadi BPCP sebagai berikut - mengingat masalah NP apa pun, ia memiliki beberapa NTM waktu polinomial yang berjalan dalam waktu p ( n ) . Kita kemudian dapat mengurangi masalah ini menjadi BPCP dalam waktu polinomial sebagai berikut - buat set domino standar dari M , kemudian tanyakan apakah ada solusi yang menggunakan domino f ( p ( n ) ) , di mana f adalah beberapa fungsi polinom yang menyatakan jumlah domino yang diperlukan agar solusi itu ada (ini mungkin kira-kira seperti n $M$$p(n)$$M$$f(p(n))$$f$$n^2$, dan tentu saja tidak eksponensial). Kemudian, menggunakan bukti yang sama yang Anda gunakan untuk menunjukkan bahwa PCP tidak dapat diputuskan, Anda dapat membuktikan bahwa ada solusi untuk instance BPCP ini yang menggunakan paling banyak petak jika jika NTM M asli menerima m dalam p ( n ) langkah. Akibatnya, kami memiliki pengurangan waktu polinomial dari setiap masalah dalam NP ke BPCP, sehingga BPCP adalah NP-hard.$f(p(n))$$M$$m$$p(n)$

(Kami juga harus menunjukkan bahwa BPCP dalam NP, tapi itu mudah; hanya menebak domino mana yang akan ditertibkan, kemudian secara pasti memverifikasi itu).

Semoga ini membantu!