Apakah bahasa lengkap NP ditutup di bawah operasi reguler?

Saya telah mencoba mencari online, tetapi saya tidak dapat menemukan pernyataan yang pasti. Masuk akal bagi saya bahwa Persatuan dan Persimpangan dua bahasa NPC akan menghasilkan bahasa yang tidak harus dalam NPC. Apakah benar juga bahwa bahasa NPC tidak ditutup di bawah operasi pelengkap, gabungan, dan bintang kleene?

complexity-theory np-complete closure-properties pengguna16742
sumber

hanya sebuah catatan: operasi reguler adalah penyatuan, penggabungan dan bintang Kleene dan bukan persimpangan dan pelengkap

A.Schulz

Mengapa tidak persimpangan dan komplemen? Saya belum melihat definisi formal operasi reguler di mana pun.

Tushar

@Tushar Memang: union, concatenation dan bintang Kleene adalah operasi reguler, sedangkan union, persimpangan dan pelengkap adalah operasi Boolean. Lihat wikipedia .

Hendrik Jan

@Tushar: Karena operasi ini digunakan untuk membangun ekspresi reguler .

A.Schulz

Jawaban:

Untuk semua contoh dalam jawaban ini, saya menggunakan alfabet $\{0,1\}$ . Perhatikan bahwa bahasa $\emptyset$ dan $\{0,1\}^*$ pasti bukan NP- lengkap.

Kelas bahasa NP- lengkap tidak ditutup di bawah persimpangan. Untuk semua bahasa NP- lengkap $L$ biarkan $L_0 = \{0w\mid w\in L\}$ dan $L_1 = \{1w\mid w\in L\}$ . $L_0$ dan $L_1$ keduanya NP -complete tetapi $L_0\cap L_1 = \emptyset$ .
Kelas bahasa lengkap NP tidak ditutup di bawah serikat. Diberikan NP- bahasa yang lengkap $L_0$ dan $L_1$ dari bagian sebelumnya, biarkan $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ dan $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ . $L'_0$ dan $L'_1$ keduanya NP -complete tetapi $L'_0\cup L'_1 = \{0,1\}^*\!$ .
Kelas bahasa NP- lengkap tidak ditutup di bawah gabungan. Pertimbangkan NP- bahasa lengkap $L'_0$ dan $L'_1$ dari bagian sebelumnya. Karena kedua bahasa berisi $\varepsilon$ , kita punya $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$ .
Kelas bahasa lengkap NP tidak ditutup di bawah bintang Kleene. Untuk semua bahasa NP- lengkap $L$ , $L\cup \{0,1\}$ adalah NP -Lengkap tapi $\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$ .
Jika kelas masalah NP- lengkap ditutup di bawah komplementasi, maka NP = coNP . Apakah ini benar atau tidak adalah salah satu masalah terbuka utama dalam teori kompleksitas.

David Richerby
sumber

Tidak termasuk pelengkap, bukankah bahasa lengkap NP ditutup di bawah semua itu? Atau apakah itu untuk P?

Adjit

@Adjit Um. Saya membuktikan bahwa NP ditutup di bawah tidak satupun.

David Richerby

Untuk bahasa spesifik Anda. Tapi saya kira saya tidak melihat bagaimana {0, 1}*tidak menyelesaikan NP. Jika Anda mengambil, misalnya, persimpangan 2 bahasa lengkap-NP seharusnya tidak Anda dapatkan bahasa lengkap-NP, dengan demikian membuat NP ditutup di bawah persimpangan?

Ajukan

{0, 1} * dan bahasa kosongnya teratur, sehingga dapat ditentukan dalam waktu polinomial dan bukan NP-Complete. @ DavidVicherby menunjukkan bahwa ada dua bahasa NP-Complete yang persimpangannya bukan NP-Complete. Itu cukup untuk membuktikan NPC tidak ditutup di bawah persimpangan.

oddev

@weirdev Tidak!

\emptyset

$\emptyset$ dan

Σ^{*}

$\Sigma^*$ bukan NP -complete karena tidak ada bahasa lain yang menguranginya. Tidak cukup hanya mengatakan bahwa mereka menggunakan P - kita tidak tahu bahwa bahasa dalam P tidak bisa NP- lengkap.

David Richerby

-2

Lihatlah bukti-bukti untuk penyatuan, persimpangan, penggabungan, dan bintang kleene dari bahasa NP, di sini . Sepertinya argumen yang sama bisa dibuat untuk bahasa NP-Complete.

Untuk notasi, biarkan

$A$ menjadi peramal yang memutuskan masalah NP-Complete yang diketahui seperti 3-SAT. Lihat definisi turing yang dapat direduksi
$L_1$ dan $L_2$ adalah bahasa NP-Lengkap
$M_1$ dan $M_2$ adalah mesin Turing yang memutuskan $L_1$ dan $L_2$ menggunakan $A$ .
$L_3$ adalah $L_1 \cup L_2$
$M_3$ adalah mesin turing yang memutuskan $L_3$

Dalam kasus penyatuan dari 1 , kita dapat membuat mesin baru $M_3$ itu yang memutuskan $L_3$ dengan menyebut $M_1$ dan $M_2$ sebagai sub rutinitas. Pada gilirannya, setiap kali $M_1$ atau $M_2$ disebut, $A$ juga disebut. Begitu $M_3$ memutuskan $L_3$ menggunakan $A$ . Dengan argumen dari 1 , waktu berjalan $M_3$ dalam P dan sejak digunakan $A$ sebagai subrutin, $L_3$ adalah NP-Lengkap. Dengan kata lain, $L_3$ adalah NP-Complete untuk alasan yang sama itu $L_1$ dan $L_2$ NP-Lengkap.

Argumen yang sama dapat dibuat persimpangan dan sepertinya argumen serupa dapat dibuat untuk penggabungan, dan bintang kleene.

Dalam kasus pujian, sepertinya sulit untuk membuktikan karena alasan yang sama sulit untuk membuktikan pujian di NP.

joebloggs
sumber

Kelengkapan NP didefinisikan dalam hal reduksi banyak orang, bukan reduksi oracle. Lebih lanjut, bahasa lengkap-NP jelas tidak ditutup di bawah persatuan atau persimpangan. Jika ditutup dengan komplemen, maka NP = coNP, yang merupakan pertanyaan terbuka utama.

David Richerby

Dalam makalah Stephen Cook tahun 1971 [1] yang mendefinisikan NP-Completeness ia menggunakan mesin Query yang konsepnya sama dengan Oracle. Anda juga harus memeriksa tautan di atas untuk memastikan reducibilitas. [1] chell.co.uk/media/product/_master/1/files/…

joebloggs

@ joebloggs: Saya dapat melihat dari argumen Anda bahwa penyatuan dan perpotongan dua bahasa NP-Complete adalah NP. Namun, itu masih tidak membuktikan apakah itu NP-lengkap. Anda harus mengurangi persatuan atau persimpangan dari dua masalah keputusan NP-lengkap ke masalah keputusan NP-lengkap untuk menunjukkan itu.

Tushar

@ DavidVicherby: Anda mengatakan bahwa bahasa NP-lengkap pasti tidak ditutup di bawah persatuan atau persimpangan. Saya tertarik melihat buktinya. Apakah Anda punya referensi untuk bukti itu?

Tushar

@ joebloggs: Argumen Anda berfungsi untuk bahasa NP, tapi BUKAN untuk bahasa NP-complete. Untuk membuktikan bahwa bahasa L adalah lengkap-Np, Anda perlu memberikan pengurangan polinomial dari L ke bahasa NP-lengkap yang dikenal. Adapun jawaban David, P ditutup di bawah persimpangan, karena bahasa kosong dan bahasa universal ada di P (karena itu, mereka juga dalam NP), tetapi mereka tidak lengkap NP. Harapan itu membuatnya jelas!

Tushar