Apakah

Apakah menyiratkan ? $\mathsf{EXP}=\mathsf{NEXP}$ $\mathsf{E}=\mathsf{NE}$

cc.complexity-theory conditional-results nexp structural-complexity argentpepper
sumber

Ya, E = NE menyiratkan EXP = NEXP yang dapat dibuktikan menggunakan argumen padding.

Mohammad Al-Turkistany

Tidak jelas bagi saya mengapa EXP = NEXP menyiratkan E = NE. Jika itu benar, maka setiap algoritma

time untuk Succinct3SAT dapat dikonversi menjadi algoritma

-time untuk Succinct3SAT. Mungkin Anda membalikkan keadaan, dan Anda bermaksud bertanya tentang implikasi lainnya?

2^{n^{k}}

$2^{n^k}$

2^{O (n)}

$2^{O(n)}$

Ryan Williams

Dan kemudian P = NP jika P = 0 atau N = 1!

Daniel Apon

Iya. Saya kira itu adalah masalah pekerjaan rumah.

Mohammad Al-Turkistany

Saya tidak mengerti penutupan pertanyaan ini sebagai "bukan pertanyaan nyata" setelah diedit menjadi pertanyaan yang masuk akal (meskipun kata-kata dari pertanyaan itu tidak menarik). Sebagai contoh, komentar Ryan Williams dapat menjadi jawaban.

Tsuyoshi Ito

Jawaban:

Ini terbuka, sejauh yang saya tahu. Ini bisa dibuktikan (karena hipotesisnya mungkin salah) atau hanya sulit untuk menunjukkan bahwa setiap algoritma time untuk Succinct3SAT dapat dikonversi menjadi algoritma waktu untuk Succinct3SAT. $2^{n^k}$ $2^{O(n)}$

Secara umum, teorema semacam ini disebut "runtuh ke bawah" yang mengatakan jika dua kelas "besar" sama, maka dua kelas "kecil" sama. Teorema ini jarang terjadi. Biasanya Anda dapat membuktikan "keruntuhan ke atas" (kelas kecil yang sama menyiratkan kelas yang lebih besar sama, seperti menyiratkan ) atau kontrapositifnya, "pemisahan ke bawah". $P = NP$ $NEXP = EXP$

Sesuatu di sepanjang garis yang Anda inginkan adalah teorema oleh Hartmanis, Immerman dan Sewelson ( http://dl.acm.org/citation.cfm?id=808769 ) bahwa $NE = E$ $\iff$ setiap set jarang di terkandung dalam . Ini memberikan "keruntuhan ke bawah" tetapi hanya untuk set yang jarang (set yang hanya berisi string dengan panjang ). $NP$ $P$ $poly(n)$ $n$

Ryan Williams
sumber