Apa yang salah dengan bukti kondisional P = NP ini?

8

Saya baru-baru ini memikirkan bukti berikut bahwa L = P menyiratkan P = NP.

Misalkan L = P. Biarkan A menjadi masalah di NP. Dengan definisi verifikasi NP, setiap solusi positif untuk A memiliki saksi yang dapat diverifikasi dalam waktu polinomial. Karena P = L, solusi yang sama dapat diverifikasi dalam ruang logaritmik. Jadi NP = NL. Tapi kemudian NL terkandung dalam P, yang berarti bahwa NP terkandung dalam P dan karenanya P = NP.

Dengan hipotesis pasar yang efisien, saya menduga bukti ini cacat. Namun saya tidak dapat menentukan sifat kesalahan yang sebenarnya. Bisakah seseorang menunjukkannya?

pengguna44898
sumber

Jawaban:

9

Misalkan L = P. Biarkan A menjadi masalah di NP. Dengan definisi verifikasi NP, setiap solusi positif untuk A memiliki saksi yang dapat diverifikasi dalam waktu polinomial. Karena P = L, solusi yang sama dapat diverifikasi dalam ruang logaritmik. Jadi NP = NL.

Anda belum menunjukkan NP itu=NL . Satu-satunya metode yang Anda peroleh untuk menunjukkan ituxA, adalah untuk "menebak" seorang saksi ydan gunakan algoritme logspace deterministik untuk memverifikasinya. Namun,yitu sendiri mungkin panjang secara polin, sedangkan mesin NL Anda hanya dapat menebak banyak bit secara logaritma: mesin NL Anda tidak memiliki cukup ruang untuk menyimpan saksi, sehingga Anda tidak memiliki algoritma NL .

Juga, perhatikan bahwa kita sudah tahu bahwa saksi untuk NP masalah -Lengkap dapat diverifikasi di kelas kompleksitas lebih kecil dari  L . Teorema Fagin mengatakan bahwa NP adalah sekumpulan masalah yang dapat didefinisikan dalam fragmen eksistensial dari logika orde kedua. Ini sama dengan mengatakan bahwa Anda dapat memverifikasi saksi panjang polinomial menggunakan logika tingkat pertama. FO benar-benar lebih lemah daripada L , karena logika tingkat pertama tidak dapat memecahkan masalah logspace sederhana seperti memberi tahu Anda jika string saksi Anda berisi jumlah genap dari 1s.

David Richerby
sumber