Apakah NP-kelengkapan / kekerasan harus konstruktif?

Apakah ada dengan properti berikut:$L\in {\bf NP}$

1. Diketahui bahwa menyiratkan .P = N $L\in {\bf P}$${\bf P}={\bf NP}$

2. Tidak ada (dikenal) waktu polinomial pengurangan Turing dari (atau beberapa masalah -Lengkap) ke .N P$SAT$${\bf NP}$$L$

Dengan kata lain, jika algoritma waktu polinomial untuk menyiratkan runtuhnya ke , maka apakah perlu bahwa "kekerasan umum" untuk harus entah bagaimana , dalam arti bahwa, katakanlah, harus dapat direduksi menjadi melalui reduksi spesifik?N P P L N $L$${\bf NP}$${\bf P}$$L$${\bf NP}$S A T $constructive$$SAT$$L$

Ya, ada set seperti itu, ambil -intermediate set (set apa saja yang terbukti -intermediate dengan asumsi ), mis. satu dari SAT menggunakan teorema Ladner.N P P ≠ N $\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$

Perhatikan bahwa Anda perlu dianggap sebagai masalah , karena itu ada di tetapi tidak lengkap untuk itu. Perhatikan juga bahwa Anda mengasumsikan bahwa jika tidak ada seperti setiap masalah non-sepele akan selesai untuk jika . Selain itu kondisi yang Anda berikan tidak menyiratkan kelengkapan sehingga pertanyaan di bagian pertama tidak sama dengan pertanyaan tentang konstruktivitas kelengkapan.N P N P P ≠ N P L N P N P = $L$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{P}\neq\mathsf{NP}$$L$$\mathsf{NP}$$\mathsf{NP}=\mathsf{P}$

Mengenai pertanyaan dalam judul, yaitu "apakah -kekerasan harus konstruktif?".$\mathsf{NP}$

Jawabannya tergantung pada apa yang kita maksud dengan "konstruktif". Secara klasik, masalah keputusan didefinisikan sebagai -hard iffN $A$$\mathsf{NP}$

yang berarti

Dan menurut teorema Cook ini setara dengan

yang berarti

Bagaimana kita dapat membuat definisi ini konstruktif? Tampaknya sudah sangat konstruktif bagi saya. Saya kira yang ingin Anda tanyakan adalah apakah kita dapat membuktikan ini untuk beberapa tanpa mengetahui apa yang secara eksplisit. Saya tidak ingat melihat bukti kekerasan seperti itu.$A$$f$

Secara klasik bahkan ketika kita tidak memiliki fungsi spesifik ada fungsi, mengatakan bahwa tidak mungkin bahwa tidak ada fungsi pengurangan setara dengan mengatakan bahwa beberapa fungsi adalah pengurangan. Untuk berbicara tentang konstruktif, kita perlu lebih perhatian. Sebagai contoh, kita dapat berbicara tentang pernyataan yang dapat dibuktikan secara klasik tetapi tidak secara konstruktif (misalnya intuitionism di mana keadaan yang berbeda dari pengetahuan matematika masuk akal, Google untuk "ahli matematika ideal" atau periksa ini ).

Secara intuitif tampaknya masuk akal bagi saya bahwa kita dapat membuktikan pernyataan seperti itu menggunakan bukti melalui kontradiksi dan tanpa memberikan fungsi pengurangan yang eksplisit. Tetapi itu tidak berarti bahwa tidak ada bukti konstruktif dari pernyataan itu. Untuk mengatakan lebih banyak bahwa tidak ada bukti konstruktif yang ada kita harus lebih spesifik: bukti di mana teori / sistem? apa yang kita maksudkan dengan bukti yang membangun?

Anda mungkin tertarik pada set kreatif, ditemukan pada [1] sebagai dugaan berlawanan dengan dugaan Berman-Hartmanis bahwa semua set NP-lengkap adalah isomorfik untuk SAT.$k$

"Isomorfik" berbeda dari reduksi Turing (faktanya jauh lebih lemah), tetapi set ini terbukti NP-hard secara langsung dan sejauh yang saya tahu tidak ada pengurangan yang diketahui untuk SAT. Yang mengatakan, dengan definisi kelengkapan NP harus ada beberapa pengurangan antara keduanya, jadi sementara ini memenuhi kriteria pengurangan "tidak diketahui" itu mungkin tidak persis apa yang Anda cari.

[1] Joseph, D. dan Young, P. Beberapa komentar tentang fungsi saksi untuk set nonpolinomial dan noncomplete dalam NP. Ilmu Komputer Teoritis. vol 39, hal 225--237. 1985. Elsevier.

Berikut ini adalah contoh untuk pertanyaan dalam judul. Itu diambil dari makalah berikut: Jan Kratochvil, Petr Savicky, dan Zsolt Tuza. Satu lagi kemunculan variabel membuat kepuasan beralih dari sepele ke np-selesai. Jurnal SIAM tentang Komputer, 22 (1): 203–210, 1993.

Misalkan f (k) adalah bilangan bulat maksimal r sehingga setiap forumula k-SAT di mana setiap variabel terjadi paling banyak r kali, adalah memuaskan. Tidak diketahui apakah f (k) dapat dihitung, meskipun batas yang relatif ketat diketahui untuk itu (lihat H. Gebauer, R. Moser, D. Scheder, dan E. Welzl. Lemma dan Kepuasan Lokal Lov ́asz. Kepuasan Algoritma, halaman 30–54, 2009.).

(k, s) -SAT adalah masalah k-SAT terbatas pada forumlas di mana setiap variabel terjadi paling banyak kali.

Kratochvil et al. membuktikan bahwa (k, f (k) +1) -SAT adalah NP-complete. Perhatikan bahwa (k, f (k)) - Masalah SAT selalu memuaskan (menurut definisi). Pengurangan itu sendiri adalah non-konstruktif: perhatikan bahwa reduksi menghasilkan rumus di mana setiap variabel terjadi paling banyak f (k) +1 kali, meskipun f (k) tidak diketahui dapat dihitung. Gagasan utama non-konstruktif adalah bahwa meskipun nilai f (k) tidak diketahui, ada rumus (k, f (k) +1) -SAT yang tidak memuaskan, dan mereka memanipulasi formula itu sesuai dengan kebutuhan mereka .

Agrawal dan Biswas menyajikan bahasa lengkap NP yang tidak ada pengurangan Karp atau Cook yang diketahui. Bukti kelengkapan mengikuti karena relasinya sebagai saksi bersifat universal (relasi saksi memiliki sambungan yang disyaratkan dan operator ekivalen yang diperlukan bersifat universal). Bahasa diberikan dalam bagian 6.3 dalam referensi.

M. Agrawal, S.Biswas, hubungan Universal dalam Prosiding IEEE Conferenceon Structure in The Complexity Theory (1992), hlm. 207–220.