Bahasa lengkap NP padat menyiratkan P = NP

Kita mengatakan bahwa bahasa adalah padat jika ada polinomial sehingga untuk semua Dengan kata lain, untuk setiap panjang diberikan hanya ada banyak kata panjang polinomi yang tidak ada dalam $J \subseteq \Sigma^{*}$ $p$

| J^{c} \cap Σ^{n} | \leq p (n)

$|J^c \cap \Sigma^n| \leq p(n)$

n \in N .

$n \in \mathbb{N}.$

n

$n$

n

$n$

J .

$J.$

Masalah yang saya pelajari saat ini meminta untuk menunjukkan yang berikut

Jika ada bahasa padat -lengkap maka $NP$ $P = NP$

Apa yang disarankan oleh teks adalah untuk mempertimbangkan reduksi polinomial menjadi - dan kemudian membuat algoritma yang mencoba memenuhi formula diberikan sembari juga menghasilkan elemen dalam $3$ $SAT$ $CNF$ $J^c.$

Yang saya ingin tahu adalah

Apakah ada bukti yang lebih langsung? Apakah gagasan ini dikenal dalam pengaturan yang lebih umum?

complexity-theory time-complexity np-complete satisfiability Jernej
sumber

Ada gagasan terkait bahasa jarang , di mana kondisinya justru sebaliknya:

| J \cap Σ^{n} | \leq p (n)

$|J \cap \Sigma^n| \leq p(n)$

Yuval Filmus

Lihat teorema Mahaney .

Pål GD

@ PålGD Berubah menjadi jawaban? (dengan asumsi argumen tersebut

mengarah

Jawaban:

Ini adalah masalah pekerjaan rumah yang bagus tentang teorema Mahaney.

Perhatikan bahwa pelengkap bahasa "padat" adalah bahasa yang jarang. Apalagi jika suatu bahasa adalah -complete pelengkapnya adalah $\mathsf{NP}$ -complete. $\mathsf{coNP}$

Jika ada "padat" bahasa -Lengkap, ada jarang $\mathsf{NP}$ bahasa -Lengkap. $\mathsf{coNP}$

Teorema Mahaney mengatakan kepada kita bahwa tidak ada jarang bahasa -Lengkap kecuali $\mathsf{NP}$ . $\mathsf{P}=\mathsf{NP}$

Kita dapat mengadopsi bukti untuk menunjukkan bahwa tidak ada bahasa yang jarang -lengkap kecuali yang setara dengan (karena $\mathsf{coNP}$ $\mathsf{P}=\mathsf{coNP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}$ ditutup di bawah komplemen).

Singkatnya, jawabannya adalah tidak kecuali . Perhatikan bahwa jika maka setiap bahasa nontrivial adalah $\mathsf{P}=\mathsf{NP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ -complete.

ps: Anda mungkin ingin mencoba yang berikut ini dan kemudian menggunakan teorema Mahaney ini: ada jarang set -Lengkap IFF ada jarang -Lengkap set. Namun saya ragu bahwa bukti untuk pernyataan ini akan jauh lebih mudah daripada bukti untuk teorema Mahaney. $\mathsf{NP}$ $\mathsf{coNP}$

Kaveh
sumber

Seperti disebutkan di atas menurut teorema Mahaney . Bahasa yang jarang dan padat tidak bisa menjadi kecuali $NP-Hard$ $P=NP$ .

Draf yang disebutkan berisi bukti lengkap.

Reza
sumber

Ini tidak memberikan lebih dari komentar (yang bahkan bukan milik Anda). Tolong jelaskan untuk membuat jawaban yang tepat dari posting ini.

Raphael

@ Raphael: Ini adalah jawaban yang tepat. Apakah Anda memeriksa tautannya?

Tsuyoshi Ito

@TsuyoshiIto: Jawaban yang hanya berisi tautan umumnya dianggap buruk di SE; lihat di sini .

Raphael

@ Raphael: Pertanyaan yang dijawab diselesaikan sebelumnya dalam literatur. Tautan berisi seluruh bukti (yaitu 6 halaman). Saya pikir jika dia memiliki lebih banyak pertanyaan, kita dapat melanjutkan dengan diskusi.

Reza

@ Raphael: Konyol. Tautan lebih baik daripada tidak sama sekali. Jika Anda mau, jelaskan jawabannya sendiri daripada menyalahkan pengguna karena memposting tautan yang bermanfaat.

Tsuyoshi Ito