Cacat di NP = Bukti CoNP saya?

12

Saya memiliki "bukti" yang sangat sederhana ini untuk NP = CoNP dan saya pikir saya melakukan sesuatu yang salah di suatu tempat, tetapi saya tidak dapat menemukan apa yang salah. Adakah yang bisa membantu saya?

Biarkan A menjadi beberapa masalah dalam NP, dan biarkan M menjadi penentu untuk A. Biarkan B menjadi pelengkap, yaitu B ada dalam CoNP. Karena M adalah penentu, Anda dapat menggunakannya untuk memutuskan B juga (balik saja jawabannya). Bukankah itu berarti bahwa kita menyelesaikan masalah NP dan CoNP dengan M yang sama?

Untuk membuatnya lebih konkret.

Biarkan A menjadi beberapa masalah NP-complete, dan biarkan M menjadi penentu untuk A. Pertimbangkan masalah B di CoNP. Kami menganggap pelengkapnya bukan-B, yang ada dalam NP, dan kemudian mendapatkan pengurangan polinom menjadi A. Kemudian kami menjalankan penentu M kami dan membalikkan jawaban kami. Dengan demikian, kami mendapatkan penentu untuk B. Ini menyiratkan B juga dalam NP.

Bolehkah saya tahu apa yang salah dengan alasan saya?

complexity-theory p-vs-np check-my-proof np bodoh
sumber

2

Seperti jawaban di bawah menjelaskan panjang lebar, Anda tidak menggunakan gagasan "penentu" dengan benar. Masalah dalam coNP bukanlah masalah dengan "penentuan NP terbalik". Ada asimetri penting dalam masalah NP antara menerima input ("ada pilihan non-deterministik yang mengarah pada penerimaan") dan menolaknya ("semua pilihan non-deterministik mengarah pada penolakan"). Argumen Anda mengandaikan bahwa untuk NP yang menolak string berarti ("ada pilihan yang tidak menentukan yang mengarah pada penolakan"), dan itu adalah cacatnya. Dengan kata lain, Anda membuat pembilang Anda tercampur.

Andrej Bauer

1

Anda mungkin menemukan jawaban untuk pertanyaan ini mencerahkan.

Raphael

@ Raphael Anehnya, pertanyaan itu tidak menyebutkan co-NP sama sekali! (Meskipun saya setuju bahwa ini adalah bacaan yang bermanfaat bagi seseorang yang tidak yakin tentang hal semacam ini.)

David Richerby

@ DavidRicherby Karena jawabannya, pada dasarnya, "gunakan definisi NP bukan intuisi yang cacat", saya berharap begitu!

Raphael

1

Aturan praktis: konstruksi "flip final state" hanya berfungsi untuk model determinstik. Pelajari bagaimana NFA gagal memahami alasannya. Lihat juga di sini dan di sini .

Raphael

16

Ada dua kemungkinan bug dalam bukti ini:

Ketika Anda mengatakan "penentu" - yang Anda maksud adalah TM deterministik. Dalam hal ini, terjemahan terbaik (untuk pengetahuan kita) dari mesin NP ke mesin deterministik dapat menghasilkan mesin yang berjalan dalam waktu eksponensial, sehingga setelah melengkapi Anda akan memiliki penentuan untuk pelengkap dalam waktu eksponensial, membuktikan bahwa (atau, setelah beberapa optimasi, ). $co-NP\subseteq EXP$ $co-NP\subseteq PSPACE$
Ketika Anda mengatakan "penentu" yang Anda maksud adalah TM yang tidak deterministik. Dalam hal ini, membalikkan jawaban tidak harus melengkapi bahasa. Memang, bahasa mesin membalik akan menjadi semua kata yang ada menjalankan menolak pada $M$ $w$

Shaull
sumber

Saya tidak yakin mengapa itu penting. Definisi saya tentang penentu adalah bahwa saya menerima jika input dalam L dan menolak jika input tidak dalam L. Penentu ini dapat bersifat deterministik atau non-deterministik. Namun, saya mengatakan bahwa L dalam NP, dan karena itu jika saya menggunakan TM non-deterministik maka saya akan mengambil waktu polinomial. Juga, boleh saya tahu mengapa membalik bit tidak selalu melengkapi bahasa. Setahu saya, CoNP = {L | bukan L \ dalam NP}. Karena itu, jika saya membalik bit saya harus mendapatkan jawabannya?

Biarkan

. Pertimbangkan TM non-deterministik yang berfungsi sebagai berikut - dalam sekali proses, selalu menghasilkan "tolak". Dalam menjalankan lain, ia mengakui

dalam waktu polinomial (mungkin sejak

). Pertimbangkan apa yang terjadi jika Anda membalik bit - proses penolakan menjadi menerima untuk setiap input, sehingga mesin yang dilengkapi mengenali

- yang bukan pelengkap kecuali

. Saya sarankan Anda meninjau dengan cermat definisi nondeterminisme untuk memahami ini sepenuhnya.

L \in N P

$L\in NP$

L

$L$

L \in N P

$L\in NP$

Σ^{*}

$\Sigma^*$

L = \emptyset

$L=\emptyset$

Shaull

Saya tidak bermaksud bahwa saya membalik bit dari setiap jalur perhitungan tunggal. Maksud saya adalah bahwa jika TM saya menerima, maka ini berarti bahwa ada jalur komputasi yang mencapai keadaan terima. Ini berarti L ada di NP, yang berarti komplemen ada di dalam CNP. Jika TM saya menolak, maka ini berarti setiap jalur komputasi menolak. Ini berarti bahwa komplemen ada dalam NP, yang berarti L ada dalam CoNP.

4

@impleton: Anda tahu bahwa NTM tidak memiliki akses ke semua jalur sekaligus, hanya satu jalur? Anda berpikir sebagai seseorang yang secara deterministik menganalisis perilaku NTM dari luar.

frafl

7

Saya pikir OP dapat mengambil manfaat dari melihat definisi NP lebih hati-hati.

MCH

15

Berikut cara lain untuk melihat titik yang dibuat Shaull sehubungan dengan "penentu".

Masalahnya adalah dalam NP jika dan hanya jika ada algoritma sedemikian rupa sehingga $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$

untuk setiap instance YA , ada sertifikat sedemikian rupa sehingga ; dan $x \in \{0,1\}^n$ $p \in \{0,1\}^{\mathrm{poly}(n)}$ $V(x,p) = 1$
untuk setiap instance NO , kami memiliki untuk semua . $x \in \{0,1\}^n$ $V(x,p) = 0$ $p \in \{0,1\}^{\mathrm{poly}(n)}$

Ini biasanya digambarkan sebagai kondisi kelengkapan dan kesehatan untuk algoritma verifikasi NP : kondisi "kelengkapan" mengatakan bahwa setiap instance YA memiliki sertifikat, dan kondisi "kesehatan" mengatakan bahwa algoritma tidak pernah dibodohi oleh instance NO. Sebaliknya untuk CoNP : ada algoritma verifikasi yang akan menerima setidaknya satu sertifikat untuk setiap instance NO, tetapi yang tidak pernah bisa dibodohi oleh instance YA.

Jika Anda ingin menunjukkan NP ⊆ coNP , Anda harus menunjukkan bahwa setiap masalah NP memiliki verifier tipe- coNP , yang dapat mensertifikasi NO instans alih-alih instance YA. Anda tidak dapat melakukan ini dengan mesin Turing nondeterministic: tidak ada cara yang kami tahu, misalnya, untuk secara efisien memetakan instance SAT satu sama lain, sedemikian rupa sehingga semua formula yang tidak memuaskan dipetakan ke yang memuaskan, dan sebaliknya. (Meniadakan output atau formula tidak cukup, misalnya: formula yang memuaskan tetapi bukan tautologi hanya akan dipetakan ke formula berbeda yang memuaskan tetapi bukan tautologi, ketika kita membutuhkan formula yang tidak memuaskan sebagai gantinya.) Tidak ada cara yang kita tahu untuk 'membodohi' mesin nondeterministik untuk mendeteksi hal-hal seperti semua jalannya menjadi jalur penolakan.

Anda mungkin bertanya: "Bukankah mesin Turing nondeterministis tahu hasil apa yang didapatnya?" Jawabannya adalah tidak , tidak. Bekerja dari mesin non-deterministik tidak memberikannya akses ke informasi apa pun tentang lebih dari satu jalur komputasi sekaligus: Anda mungkin berpikir itu bekerja di banyak jalur secara paralel, tetapi dalam setiap jalur itu hanya tahu tentang satu jalur itu. Jika Anda mencoba melengkapinya dengan kemampuan untuk "menyadari" apakah ada atau tidak ada solusi sebagai titik tertentu, Anda malah menggambarkan mesin dengan NP oracle , yang lebih (berpotensi!) Lebih kuat daripada mesin Turing sederhana nondeterministic.

$\Delta_2^{\mathrm P}$ $\mathsf{P}^{\mathsf{NP}}$ $\mathsf{P}^{\mathsf{NP}}$
$\Sigma_2^{\mathrm P}$ $\mathsf{NP}^{\mathsf{NP}}$ $\mathsf{P}^{\mathsf{NP}}$ memiliki jawaban TIDAK karena ramalan itu, tetapi masih akan terjebak untuk beroperasi di dalam salah satu cabang komputasinya sendiri (yang cukup kuat), sehingga ia tidak dapat mengetahui apakah semua cabang komputasinya sendiri menolak.

$\mathsf{NP}$ $\mathsf{NP}^{\mathsf{NP}}$

Jadi, tidak, tidak ada mesin (deterministik atau lainnya) yang dapat dengan mudah 'memutuskan' bahwa masalah adalah contoh YA atau TIDAK secara efisien, kecuali jika kita menggunakan nubuat; tetapi bahkan dengan oracle seperti itu, kita berakhir dengan mesin yang (mungkin) lebih kuat daripada NP atau coNP , bukan yang menunjukkan bahwa mereka setara.

Niel de Beaudrap
sumber

Hai, terima kasih untuk Anda dan Shauli atas komentarnya. Apakah Anda mengatakan bahwa NTM dapat mengenali bahasa NP dalam polytime, tetapi tidak dapat memutuskan bahasa NP dalam polytime? Saya pikir itulah yang saya asumsikan ketika saya mengatakan bahwa saya memiliki penentu untuk masalah NP.

simpleton

2

P^{N P}

$P^{NP}$

N P \subset P^{N P}

$NP \subset P^{NP}$

C o N P \subset P^{N P}

$CoNP \subset P^{NP}$

U N S A T \in N P

$UNSAT \in NP$

5

Kekerasan NP didefinisikan dengan banyak-satu reduksi, bukan reduksi oracle.

Yuval Filmus

6

Alasan Anda menyiratkan bahwa RE = CORE, tetapi ini terbukti salah. Anda dapat mencoba mencari bukti tentang itu dan kemudian melihat di mana pengurangan Anda gagal.

$\{ x : P \text{ halts on input } x \}$ $\{ x : (x,w) \in L' \text{ for some } w \}$ $L'$

$L = \{ x : p \text{ halts on input } x \}$ $L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$ $L'$ $L = \{ x : (x,w) \in L' \text{ for some } w \}$

$L = \{ x : (x,w) \in L' \text{ for some } w \}$ $L'$ $P(x,w)$ $Q(x)$ $w$ $P(x,w)$ $w$ $P(x,w)$ $w$ $Q$ $L = \{ x : Q \text{ halts on input } x \}$

$L = \{(P,x) : P \text{ halts on input x}\}$ $P$ $x$ $H$ $H(P,x)$ $(P,x) \notin L$ $G$ $G(x)=H(x,x)$ $(G,G) \in L$ $G$ $G$ $H$ $(G,G)$ $(G,G) \notin L$ $(G,G) \notin L$ $G$ $G$ $H$ $(G,G)$ $(G,G) \in L$ $H$

$H$

Yuval Filmus
sumber

2

Berikut adalah TL; versi DR; Saya juga memposting jawaban yang lebih panjang untuk pertanyaan serupa.

$A$ $M$ $x\in A$ $M$ $x$ $M$ $x$ . Jika Anda hanya membalik keadaan penerimaan dan penolakan, Anda akan beralih dari mesin yang memiliki beberapa jalur penerimaan dan beberapa jalur penolakan ke mesin yang memiliki beberapa jalur penolakan dan beberapa jalur penerima. Dengan kata lain, ia masih memiliki jalur penerimaan, jadi ia masih menerima. Membalik keadaan terima dan tolak dari mesin nondeterministik tidak, secara umum, menyebabkan Anda menerima bahasa pelengkap.

Asimetri definisi ini (terima jika ada jalur yang menerima; tolak saja jika semua jalur ditolak) yang membuat masalah NP vs ko-NP menjadi sulit.

David Richerby
sumber

-2

Saya benar-benar setuju bahwa mesin nondeterministic Anda M dapat memutuskan apakah string input yang diberikan dalam B. Namun, "memutuskan" sedikit berbeda dari cara memutuskan jika input yang diberikan adalah dalam A. Dalam kasus terakhir, ia melakukannya dengan ( nondeterministically) menemukan negara penerima. Dalam kasus sebelumnya, ia melakukannya dengan gagal menemukan negara penerima. Mengapa perbedaan ini penting? Ayo lihat:

Saat bertanya M "Apakah string dalam bahasa A?"

M mencapai status penerimaan. Ini, Anda dapat membuktikan (lihat, misalnya, teorema buku Sipser 7.20) menyiratkan bahwa ada mesin deterministik yang memverifikasi string dalam A dalam waktu polinomial

Ketika menanyakan M "Apakah string dalam bahasa B?"

M mencapai status tolak pada semua cabang perhitungan nondeterministiknya. Jika Anda berpikir tentang cara kerja bukti verifikasi di atas, Anda akan melihat bahwa itu tidak dapat diselesaikan dalam situasi ini. Ini kira-kira karena verifier menggunakan jalur yang diambil M melalui ruang keadaannya sebagai "bukti". Dalam hal ini, tidak ada jalan seperti itu.

Kesimpulan:

Jika Anda menganggap keberadaan verifier deterministik waktu polinomial untuk suatu bahasa sebagai definisi bahasa NP (yang seharusnya), keberadaan M tidak membuktikan bahwa B ada dalam NP.

Alex
sumber

1

M

$M$

B

$B$

B

$B$

M

$M$

Cacat di NP = Bukti CoNP saya?

Jawaban:

Saat bertanya M "Apakah string dalam bahasa A?"

Ketika menanyakan M "Apakah string dalam bahasa B?"

Kesimpulan: