Mengapa persamaan antara kelas kompleksitas diterjemahkan ke atas dan bukan ke bawah?

Hai teman-teman, saya mengerti bahwa trik padding memungkinkan kita menerjemahkan kelas kompleksitas ke atas - misalnya . Padding berfungsi dengan "menggembungkan" input, menjalankan konversi (katakanlah dari katakanlah ke ), yang menghasilkan algoritma "ajaib" yang dapat Anda jalankan pada input yang empuk. Meskipun ini masuk akal secara teknis, saya tidak bisa mendapatkan intuisi yang bagus tentang cara kerjanya. Apa sebenarnya yang terjadi di sini? Apakah ada analogi sederhana untuk apa itu padding?$P=NP \rightarrow EXP=NEXP$$NP$$P$

Dapatkah memberikan alasan yang masuk akal mengapa hal ini terjadi?

Saya pikir cara terbaik untuk mendapatkan intuisi untuk masalah ini adalah dengan memikirkan apa masalah lengkap untuk kelas waktu eksponensial. Sebagai contoh, masalah lengkap untuk NE adalah masalah standar NP-lengkap pada input yang dijelaskan secara ringkas, misalnya, diberi sirkuit yang menggambarkan matriks kedekatan suatu grafik, apakah grafik 3-berwarna? Kemudian masalah apakah E = NE menjadi setara dengan apakah masalah NP dapat dipecahkan dalam waktu polinomial pada input yang dijelaskan secara ringkas, misalnya, yang dengan kompleksitas Kolmogorov kecil yang efektif. Ini jelas tidak lebih kuat dari apakah mereka dapat dipecahkan pada semua input. Semakin besar batas waktu, semakin kecil kompleksitas Kolmogorov dari input yang relevan, sehingga runtuh untuk batas waktu yang lebih besar berlaku pada algoritma yang bekerja pada subset input yang lebih kecil.

Russell Impagliazzo

OK, jadi tujuan Anda adalah untuk menunjukkan bahwa berdasarkan C L A S S 1 [ g ( n ) ] = C L A S S 2 [ h ( n ) $CLASS_1[g(f(n))] = CLASS_2[h(f(n))]$$CLASS_1[g(n)] = CLASS_2[h(n)]$(kami tidak menentukan apa sebenarnya kelas-kelas ini, kami hanya tahu bahwa mereka entah bagaimana ditentukan dengan ukuran input). Kami memiliki bahasa , diputuskan oleh beberapa algoritma A . Sekarang kita membuat bahasa L ′ dengan melapisi setiap kata dalam x ∈ L , sehingga panjangnya sekarang f ( n ) , dan kita melihat bahwa itu terkandung dalam C L A S S 1 [ $L \in CLASS_1[g(f(n))]$$A$$L'$$x \in L$$f(n)$ (algoritme baru kami A ′ pada dasarnya hanya mengabaikan angka nol yang ditambahkan dan menjalankan A pada input pendek dan nyata).$CLASS_1[g(n)]$$A'$$A$

Apa yang kami lakukan adalah: kami mengambil bahasa dari kelas yang lebih besar dan kami membalutnya, sehingga dapat diselesaikan dengan algoritma yang lebih lemah yang memberi kami penahanan di kelas yang lebih kecil - algoritma yang lebih lemah dapat melakukannya, karena memiliki jumlah yang sama dari 'pekerjaan nyata' untuk dilakukan seperti sebelumnya, tetapi memiliki batasannya (menjadi fungsi dari panjang input) diangkat dengan memperluas input.

Sekarang kita tahu bahwa dan karenanya L ′ ∈ C L A S S 2 [ h ( n ) ] (diputuskan oleh beberapa algoritma B ′ ). Kami ingin pergi dari sini ke L ∈ C L A S S 2 [ h ( f ( n ) ) $L' \in CLASS_1[g(n)]$$L' \in CLASS_2[h(n)]$$B'$$L \in CLASS_2[h(f(n))]$. Tapi itu mudah - algoritma memutuskan L hanya bantalan masukan yang sesuai dan berjalan B ' pada input empuk.$B$$L$$B'$

Langkah ini dapat diringkas sebagai berikut: kami ingin memutuskan di kelas yang lebih besar, lebih banyak akal. Dengan menggunakan sumber daya tambahan, kami mengisi input dan menjalankan algoritme untuk menentukan bahasa yang empuk$L$ .

Tentu saja ada beberapa detail teknis yang terlibat di sini (karena kita harus memastikan bahwa padding dapat diimplementasikan di kelas yang kita pertimbangkan) tetapi saya mengabaikannya untuk memberikan intuisi umum.

Saya melihat argumen padding dalam hal kekompakan representasi. Pikirkan dua mesin penerjemah Turing: meledakkan instance, dan C kompres lagi.$B$$C$

Argumen padding bekerja dengan , dengan menyusun B dengan versi deterministik TM untuk bahasa di kelas nondeterministic yang lebih rendah. Keluaran B secara kolektif membentuk bahasa yang tidak direpresentasikan secara kompak, jadi ini menjadi "lebih mudah".$B$$B$$B$

Tidak mungkin menerapkan ide dengan cara lain, menggunakan , karena hanya beberapa bahasa di kelas yang mudah dihasilkan dengan meledakkan bahasa di kelas keras.$C$

Untuk membuatnya lebih intuitif mari kita lihat apa yang terjadi lebih abstrak!

Kami memiliki dua transformasi, satu untuk input dan satu untuk masalah. Saya akan menunjukkan keduanya dengan , itu akan menjadi jelas dari konteks ketika itu adalah yang pertama dan ketika itu adalah yang kedua.$pad$

Dua transformasi ini memiliki properti berikut:

I. untuk semua masalah , untuk semua input x ∈ Σ ∗ :$A\subseteq \Sigma^{ * }$$x\in\Sigma^{ * }$

iff x ∈ A ,$pad(x) \in pad(A)$$x \in A$

II jika ada di E X P ( N E X P ), maka p a d ( A ) ada di P ( N P ).$A$$EXP$$NEXP$$pad(A)$$P$$NP$

AKU AKU AKU. transformasi untuk input dalam kelas kompleksitas ,$EXP$

Jelas bahwa transformasi untuk bantalan memiliki sifat-sifat ini.

Sekarang, alasan bahwa kita tidak tahu bagaimana melakukan hal yang sama di arah sebaliknya adalah bahwa kita tidak memiliki transformasi seperti padding di arah sebaliknya (ketika kita bertukar dengan P dan N E X P dengan N P ). Jadi pertanyaannya adalah mengapa?$EXP$$P$$NEXP$$NP$

Saya tidak memiliki argumen formal mengapa tidak ada transformasi seperti itu pada saat ini, tetapi secara intuitif apa yang dikatakan András Salamon benar. Mudah untuk menambah ukuran input, tetapi tidak jelas bagaimana mereka dapat dikompresi?

Cara lain untuk memahaminya adalah dengan memikirkannya dengan cara berikut. Asumsikan bahwa , dan kami ingin menyelesaikan masalah N E X P = N T i m e ( 2 n O ( 1 ) ) . Kami diberi input x panjang n , kami menganggapnya sebagai input dengan panjang N = 2 n O ( 1 ) :$P=NP$$NEXP=NTime(2^{n^{O(1)}})$$x$$n$$N=2^{n^{O(1)}}$

$NEXP(n) = NTime(2^{n^{O(1)}}) = NTime(N) \subseteq NP(N) \subseteq P(N) = Time(N^{O(1)}) = Time(2^{n^{O(1)}}) = EXP(n)$