Teorema Ladner Umum

Teorema Ladner menyatakan bahwa jika P ≠ NP, maka ada hierarki tak terbatas dari kelas kompleksitas yang secara ketat berisi P dan secara ketat terkandung dalam NP. Buktinya menggunakan kelengkapan SAT di bawah banyak-satu pengurangan NP. Hirarki berisi kelas kompleksitas yang dibangun oleh semacam diagonalisasi, masing-masing berisi beberapa bahasa yang bahasa di kelas bawahnya tidak banyak-satu dapat direduksi.

Ini memotivasi pertanyaan saya:

Biarkan C menjadi kelas kompleksitas, dan biarkan D menjadi kelas kompleksitas yang secara ketat berisi C. Jika D berisi bahasa yang lengkap untuk beberapa gagasan pengurangan, apakah ada hierarki kelas kompleksitas tak terbatas antara C dan D, sehubungan dengan pengurangan?

Lebih khusus lagi, saya ingin tahu apakah ada hasil yang dikenal untuk D = P dan C = LOGCFL atau C = NC , untuk gagasan pengurangan yang tepat.

Makalah Ladner sudah menyertakan Teorema 7 untuk kelas C yang dibatasi ruang, seperti yang ditunjukkan Kaveh dalam sebuah jawaban. Dalam bentuknya yang paling kuat, ini mengatakan: jika NL ≠ NP maka ada urutan bahasa yang tak terbatas antara NL dan NP, yang tentu saja meningkatkan kekerasan. Ini sedikit lebih umum daripada versi biasanya (Teorema 1), yang tergantung pada P ≠ NP. Namun, makalah Ladner hanya mempertimbangkan D = NP.

Jawaban atas pertanyaan Anda adalah "ya" untuk berbagai kelas dan reduksi, termasuk reduksi ruang log dan kelas yang Anda sebutkan, seperti yang dibuktikan dalam makalah ini:

H. Vollmer. Teknik kesenjangan bahasa ditinjau kembali . Logika Ilmu Komputer, Catatan Kuliah di Ilmu Komputer Vol. 533, halaman 389-399, 1990.

K. Regan dan H. Vollmer. Bahasa gap dan kelas kompleksitas waktu log . Ilmu Komputer Teoritis, 188 (1-2): 101-116, 1997.

(Anda dapat mengunduh file postscript gzipped dari makalah ini di sini .)

Buktinya mengikuti prinsip dasar perpanjangan Uwe Schöning tentang teorema Ladner:

Uwe Schöning. Pendekatan yang seragam untuk mendapatkan set diagonal dalam kelas kompleksitas . Ilmu Komputer Teoritis 18 (1): 95-103, 1982.

Bukti Schöning selalu menjadi bukti favorit saya tentang teorema Ladner - itu sederhana dan umum.

Sangat mungkin bahwa Anda dapat melakukan ini dalam pengaturan umum. Hampir bisa dipastikan hasil seperti itu telah dibuktikan dalam suasana generik, tetapi referensi tersebut luput dari saya saat ini. Jadi, inilah argumen dari awal.

Penulisan di http://oldblog.computationalcomplexity.org/media/ladner.pdf memiliki dua bukti teorema Ladner. Bukti kedua, oleh Russell Impagliazzo, menghasilkan bahasa dari bentuk { x 01 f ( | x | ) } di mana x mengkodekan rumus yang memuaskan dan f adalah fungsi waktu komputasi polinomial tertentu. Artinya, dengan hanya mengisi SAT dengan angka 1 yang tepat , Anda bisa mendapatkan set "NP-intermediate". Padding dilakukan untuk "mendiagonalisasi" atas semua kemungkinan pengurangan waktu polinomial, sehingga tidak ada pengurangan waktu polinomial dari SAT ke L $L_1$$x01^{f(|x|)}$$x$$f$$1$$L_1$akan bekerja (dengan asumsi ). Untuk membuktikan bahwa ada banyak tingkat kekerasan, seseorang harus dapat menggantikan L 1 sebagai pengganti SAT dalam argumen di atas, dan ulangi argumen untuk L 2 = { x 0 1 f ( | x | ) | x ∈ L 1 }. Ulangi dengan L i = { x 0 1 f ( | x | ) | x ∈ L i $P \neq NP$$L_1$$L_2 =$$x 0 1^{f(|x|)} | x \in L_1$$L_i =$ }.$x 0 1^{f(|x|)} | x \in L_{i-1}$

Tampak jelas bahwa bukti semacam itu dapat digeneralisasi ke kelas dan D , di mana (1) C terkandung dalam D , (2) D memiliki bahasa lengkap di bawah pengurangan- C , (3) daftar semua pengurangan- C dapat secara rekursif disebutkan, dan (4) fungsi f adalah dihitung di C . Mungkin satu-satunya persyaratan yang mengkhawatirkan adalah yang terakhir, tetapi jika Anda melihat definisi f dalam tautan, itu terlihat sangat mudah untuk dihitung, untuk sebagian besar kelas C yang masuk akal yang dapat saya pikirkan.$C$$D$$C$$D$$D$$C$$C$$f$$C$$f$$C$

Saya kira jawabannya adalah positif untuk dan versi seragam N C . Bukti Ladner tidak menggunakan banyak hal selain dari apa yang Anda nyatakan dan fakta bahwa kelas yang lebih kecil diwakili secara rekursif dan harus bekerja dengan modifikasi kecil tapi saya belum memeriksa detailnya, lihatlah tulisan Lance di sini .$C=L$$NC$

Memperbarui

Periksa kertas Ladner Pada Struktur Pengurangan Waktu Polinomial

Berikut ini abstraknya: Dua konsep reducibilitas waktu polinomial, dilambangkan di sini oleh dan ≤ P m , masing-masing didefinisikan oleh Cook dan Karp. Properti abstrak dari dua relasi ini pada domain set yang dapat dihitung diselidiki. Kedua hubungan terbukti padat dan memiliki pasangan minimal. Lebih jauh lagi, ada urutan ketat naik dengan sepasang minimal batas atas ke urutan. Metode kami menunjukkan kepadatan menghasilkan hasil bahwa jika P ≠ N P maka ada anggota N P - P yang tidak lengkap polinomial.$\leq_T^P$$\leq_m^P$$P \neq NP$$NP - P$

$P$$A$$A \not \in P$$A \leq_m^P B$$B \not \leq_T^P A$

Juga lihat bagian 6 yang membahas generalisasi:

$C$$\leq_m^C$$\leq_T^C$$P$$C$

$C$$\leq_m^C$$\leq_T^C$$P$$C$

Istilah waktu kelas dan kelas ruang didefinisikan dalam makalah.

Saya mengajukan pertanyaan serupa dengan Peter Shor di Mathoverflow di sini . Menurutnya, dia tidak mengetahui hasil seperti itu.

$NP\neq P$

$A$$\sum_i^p$$B \in \sum_{i-1}^p$$B$

Masalah lain yang menarik adalah untuk mempertimbangkan generalisasi dari Ladner ke versi janji dari kelas semantik, seperti janji BPP, berjanji, dll.