Apakah dugaan isomorfisme menyiratkan batas bawah eksponensial pada kepadatan saksi?

The isomorfisma Dugaan dari Berman dan Hartmanis menyatakan bahwa semua -Lengkap set waktu polinomial isomorfik satu sama lain. Ini berarti bahwa masalah lengkap dapat direduksi secara efisien satu sama lain melalui waktu polinomial yang dapat dihitung dan biopsi yang tidak dapat dibalik. Dugaan ini mengimplikasikan . $NP$ $NP$ $P\neq NP$

Dugaan isomorfisme menyiratkan batas bawah eksponensial pada kepadatan set $NP$ lengkap karena masalah Kepuasan padat. Saya bertanya-tanya apakah itu juga menyiratkan batas bawah eksponensial pada kepadatan saksi untuk set $NP$ lengkap.

Apakah dugaan isomorfisme menyiratkan batas bawah eksponensial pada kepadatan saksi? Apakah ini menyiratkan bahwa masalah $NP$ lengkap tidak dapat di $FewP$ ?

Hasil terbaik yang saya ketahui adalah sebagai berikut:

Jika $P=UP$ dan $NP=EXP$ maka dugaan isomorfisme berlaku.

Densitas $D$ dari himpunan $S$ mengacu pada jumlah string dengan panjang kurang dari $n$ dalam bahasa. Himpunan $S$ secara eksponensial padat jika densitasnya adalah $D=\Omega(2^{n^\epsilon})$ untuk beberapa $\epsilon \gt 0$ dan untuk banyak $n$ dan jarang jika $D$ = $O(poly(n))$ .

cc.complexity-theory structural-complexity Mohammad Al-Turkistany
sumber

Saksi kepadatan set tergantung pada jumlah maksimum saksi untuk atas semua .

X

$X$

x

$x$

x \in X

$x \in X$

Mohammad Al-Turkistany

Sepertinya tidak mungkin. Akan menarik untuk membangun sebuah oracle di mana dugaan isomorfisma berlaku dan atau ... (Perhatikan bahwa membuat dapat membuat hidup sedikit lebih sulit dalam konstruksi ini, karena untuk mendapatkan dugaan isomorfisme untuk menahan seseorang kemudian akan membutuhkan , namun masih membutuhkan cara lain dalam dugaan Joseph-Young.)

N P = U P

$NP=UP$

N P = F e w P

$NP=FewP$

N P = U P

$NP=UP$

P \neq U P

$P \neq UP$

Joshua Grochow

Saya tidak melihat bagaimana itu akan segera mengikuti: dugaan isomorfisme adalah tentang bahasa, dan tampaknya tidak memiliki implikasi tentang struktur saksi verifier NP. (Setiap bahasa memiliki banyak verifier yang berbeda untuk itu, dan Anda berpotensi mencurangi verifier tersebut untuk melakukan hal-hal aneh.)

Tetapi pertanyaan Anda mengungkapkan pertanyaan lain yang sangat menarik, tentang penguatan dugaan Isomorfisme berikut ini:

"Apakah semua verifier untuk set NP-lengkap isomorfik waktu-poli?"

Yaitu, kami ingin tidak hanya isomorfisma poli waktu antara dua bahasa NP-lengkap didefinisikan oleh verifier , tetapi juga isomorfisma antara pasangan input-saksi mereka yang menghormati isomorfisme . (Catatan: Ada beberapa cara yang secara formal dapat didefinisikan oleh seseorang.) Semua bukti kekerasan yang dapat saya pikirkan memberi Anda korespondensi satu-ke-satu dari jenis ini, juga. "Konjektur Isomorfisme Saksi" yang lebih kuat ini akan menyiratkan semacam jawaban ya untuk pertanyaan Anda. $\phi_{L,L'}$ $L,L'$ $V,V'$ $\psi_{V,V'}$ $\phi_{L,L'}$ $NP$

Pencarian Google cepat (mengetik 'saksi dugaan isomorfisme') menemukan survei dari beberapa pendekatan untuk pertanyaan semacam ini:

Eric Allender. Investigasi Mengenai Struktur Set Lengkap. Perspektif dalam Kompleksitas Komputasi: Volume Peringatan Hari Jadi Somenath Biswas, Springer, 2014

Ryan Williams
sumber

+1 Sangat menarik. Mengikuti saran Anda, saya mencari di Google dan menemukan makalah ini, pengurangan Saksi-isomorfik dan masalah pencarian lokal . Apakah ini saksi isomorfisme yang diminta ?

Mohammad Al-Turkistany

Menarik! Apakah Anda ingin mengatakan bahwa untuk setiap yang -complete, terdapat verifier dan isomorfisme yang kompatibel ? Atau benar-benar untuk setiap pasangan verifier , apakah ada iso yang kompatibel? Karena gagasan Anda tentang isos yang kompatibel secara khusus menyiratkan pengurangan pelit dua arah, pertanyaan kedua mudah dipalsukan: ambil verifier untuk SAT, lalu biarkan menjadi verifier untuk SAT yang menerima setiap saksi di .

L, L^{'}

$L,L'$

N P

$\mathsf{NP}$

V, V^{'}

$V,V'$

ϕ_{L, L^{'}}, ψ_{V, V^{'}}

$\phi_{L,L'}, \psi_{V,V'}$

V, V^{'}

$V,V'$

V

$V$

V^{'}

$V'$

{{0, 1}^{n} w | V (w) = 1}

$\{\{0,1\}^n w | V(w)=1\}$

Joshua Grochow

Benar, Anda harus berhati-hati dalam merumuskan dugaan untuk menghindari contoh tandingan yang sepele. Googling mengungkapkan kepada saya bahwa saya bukan yang pertama, jadi saya sarankan membaca karya orang-orang yang telah memikirkan hal ini selama lebih dari 10 menit :)

Ryan Williams

Ryan, saya pikir dugaan Anda sangat penting. Mungkin lebih mudah untuk dibuktikan daripada dugaan Isomorfisme Berman dan Hartmanis standar. Saya pikir dugaan Anda menyarankan keberadaan verifier universal untuk semua set NP.

Mohammad Al-Turkistany

Apakah dugaan isomorfisme menyiratkan batas bawah eksponensial pada kepadatan saksi?

Jawaban: