Masalah NP-complete "Hampir mudah"

Katakanlah bahasa adalah P -density-close jika ada algoritma waktu polinomial yang memutuskan pada hampir semua input dengan benar. $L$ $L$

Dengan kata lain, ada P , sehingga menghilang, yang berarti Ini juga berarti bahwa pada input acak yang seragam, algoritma polytime untuk akan memberikan jawaban yang benar untuk dengan probabilitas mendekati 1. Oleh karena itu, masuk akal untuk melihat hampir mudah. $A\in$ $L\Delta A$

lim_{n \to \infty} \frac{| (L Δ A) \cap {0, 1}^{n} |}{2^{n}} = 0.

$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$

A

$A$

L

$L$

L

$L$

Perhatikan bahwa $L\Delta A$ tidak harus jarang. Sebagai contoh, jika ia memiliki string $2^{n/2}$ $n$ bit, maka ia masih menghilang (pada tingkat eksponensial), karena $2^{n/2}/2^n=2^{-n/2}$ .

Tidak sulit untuk (secara artifisial) membangun masalah NP- lengkap yang P -density-close, menurut definisi di atas. Misalnya, biarkan $L$ menjadi bahasa NP- lengkap, dan tentukan $L^2=\{xx\,|\, x\in L\}$ . Kemudian $L^2$ mempertahankan kelengkapan-NP , tetapi memiliki paling banyak $2^{n/2}$ $n$ -bit ya-instance. Oleh karena itu, algoritma sepele yang menjawab "tidak" untuk setiap input, akan memutuskan dengan benar $L^2$ pada hampir semua input; itu hanya akan salah pada $\leq 1-2^{-n/2}$ fraksi dari input $n$ bit.

Di sisi lain, akan sangat mengejutkan jika semua masalah NP - complete adalah P -density-close. Ini berarti bahwa, dalam arti tertentu, semua masalah NP- lengkap hampir mudah. Ini memotivasi pertanyaan:

Dengan asumsi P $\neq$ NP , yang merupakan beberapa masalah NP- lengkap alami yang tidak P -kepadatan-tutup?

cc.complexity-theory ds.algorithms complexity-classes np-complete Andras Farago
sumber

Karena Heuristica tidak dikesampingkan, bahkan tidak ada masalah yang tidak perlu-alam yang P ≠ NP diketahui menyiratkan bahwa masalahnya bukan hampir di P.

Saya percaya bahwa masalah pos korespondensi adalah masalah kandidat yang baik. Sulit bahkan untuk contoh acak yang seragam dan karenanya sulit dalam kasus rata-rata.

Mohammad Al-Turkistany

FYI: Nomenklatur pilihan Anda, walaupun wajar, bertentangan dengan beberapa nomenklatur yang ada: Kelas Almost-P terdiri dari bahasa-bahasa L sedemikian sehingga memiliki ukuran 1. Anda mungkin juga tertarik untuk ketahuilah bahwa versi definisi Anda yang jarang telah digunakan dan memiliki koneksi ke beberapa ide lain, lihat P-tutup . Mengingat definisi P-close, mungkin nama yang bagus untuk konsep Anda adalah P-density-close, atau P-close-enough :).

{A : L \in P^{A}}

$\{A : L \in P^A\}$

Joshua Grochow

Di sisi lain, masalah keputusan " Pewarnaan Grafik " agaknya adalah kandidat untuk masalah seperti itu.

$\;$

Saya tidak yakin ini adalah definisi yang tepat. Jika kepadatan menghilang maka itu "hampir mudah" melalui bahasa sepele , tidak peduli seberapa sulit sebenarnya. Namun sulit untuk menunjukkan bahasa keras alami lebih dari alfabet dengan kepadatan yang tidak hilang, hanya karena penyandian. Haruskah persimpangan tidak dengan ukuran input yang valid (jadi ini adalah masalah yang menjanjikan), daripada semua string? Kalau tidak, ini terutama memerlukan menjawab pertanyaan: apakah ada pengkodean Boolean dari beberapa bahasa NP-hard dengan kepadatan yang tidak hilang?

L

$L$

A

$A$

{0, 1}

$\{0,1\}$

n

$n$

András Salamon

Saya melihat apakah ada hipotesis yang diterima secara umum dalam teori kompleksitas, yang menyiratkan bahwa harus ada bahasa lengkap NP yang tidak dapat diterima dalam waktu polinomial pada hampir semua input (seperti yang didefinisikan dalam pertanyaan).

Menariknya, hipotesis paling "standar" tampaknya tidak menyiratkannya. Artinya, tampaknya tidak mengikuti (kecuali saya mengabaikan sesuatu) dari P NP , P BPP , NP neq coNP , E NE , EXP neq NEXP , NP PSPACE , NP EXP , NP P / poli, PH tidak runtuh, dll. $\neq$ $=$ $\neq$ $\neq$ $\neq$ $\neq$ $\neq$ $\not\subseteq$

Di sisi lain, saya menemukan satu, sedikit kurang standar, hipotesis, yang tidak menyiratkan adanya masalah NP- lengkap dicari , meskipun bukan yang alami. Dalam teori pengukuran sumber daya terbatas hipotesis mendasar adalah bahwa NP tidak memiliki -mengukur nol, dilambangkan dengan NP . Secara tidak resmi, ini berarti bahwa NP-bahasa dalam E tidak membentuk subset yang dapat diabaikan. Untuk detailnya, lihat survei di sini . Dalam teori ini mereka membuktikan, di antara banyak hal lain, bahwa NP menyiratkan adanya P $p$ $\mu_p($ $)\neq 0$ $\mu_p($ $)\neq 0$ -bi-imun dalam NP . Sebuah bahasa adalah P -bi-kekebalan tubuh jika tidak atau pelengkap memiliki bagian yang tak terbatas di P . Bahasa seperti itu memenuhi persyaratan kami dengan cara yang kuat. $L$ $L$

Namun, masih belum jelas apakah ada contoh yang mewakili masalah alami .

Andras Farago
sumber

Bi-imunitas juga jauh lebih kuat daripada kondisi Anda, dan terkait dengan penggunaan yang lebih umum dari "hampir semua" dalam teori kompleksitas struktural, yaitu "untuk semua tapi banyak sekali" ...

Joshua Grochow

@ JoshuaGrochow saya setuju, tetapi tampaknya, dalam arti tertentu, P-bi-imunitas berarti terlalu keras kepala. Tampaknya tidak terjadi di antara masalah NP-lengkap alami. Sangat mengejutkan bagi saya bahwa ternyata tidak ada hasil yang menyediakan kondisi hanya untuk keberadaan bahasa NP-complete yang sulit "hampir hampir di semua tempat". Dengan "hampir lemah di mana-mana", maksud saya bahwa kondisi "semuanya tetapi sangat banyak" digantikan oleh "semua tetapi semakin banyak". Itu mungkin berhubungan lebih baik dengan apa yang sebenarnya ditemui dalam praktik.

Andras Farago

Apakah NP diketahui dapat diukur?

@ RickyDemer Sejauh yang saya tahu, tidak diketahui apakah NP dapat diukur p.

Andras Farago

Masalah NP-complete "Hampir mudah"

Jawaban: