Hambatan untuk memisahkan kelas kompleksitas lainnya

Do Alam Bukti , perelatifan dan Algebrization juga mempengaruhi pemisahan kelas kompleksitas lain seperti dll?$L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$

Misalnya bukti alami penghalang harus mempengaruhi bukti karena akan memisahkan P ≠ N P . Namun hubungan antara N P dan C o N P tampaknya tidak memiliki banyak dengan OWFs dibandingkan dengan hubungan antara P dan N P . Jadi apakah bukti alami memengaruhi pemisahan N P ≠ C o N P yang lebih kuat ?$NP\neq CoNP$$P\neq NP$$NP$$CoNP$$P$$NP$$NP\neq CoNP$

Ada (setidaknya) dua area di mana hambatan yang ada tidak banyak bicara:

ACC Batas Bawah Tidak ada penghalang yang diketahui untuk membuktikan bahwa TC0 tidak dalam ACC (tidak seragam) - selain kemungkinan bahwa pemisahan itu mungkin salah. Tidak jelas apakah penghalang Bukti Alami harus berlaku untuk ACC. Pertanyaannya adalah: haruskah kita berharap ada fungsi pseudorandom yang dapat diterapkan dalam ACC?

LOGSPACE vs NP Seperti yang ditunjukkan oleh Fortnow , mekanisme oracle yang ada untuk perhitungan ruang-terbatas tampaknya tidak menghadirkan penghalang nyata untuk LOGSPACE vs NP. Sepengetahuan saya, model oracle yang dikenal yang menghasilkan runtuhnya LOGSPACE dan NP juga runtuh ALTERNATING LOGSPACE (yaitu, P) dan ALTERNATING POLYTIME (yaitu, PSPACE), maka ramalan ini memperlakukan model komputasi bolak-balik secara tidak konsisten dengan kenyataan (karena LOGSPACE tidak sama dengan ke PSPACE).

Hasil Razborov dan Rudich dalam kertas bukti alami mereka cukup umum. Hal ini tidak terbatas pada vs N P .$\mathsf{P}$$\mathsf{NP}$

Saya pribadi menyukai kejelasan penjelasan dalam buku terbaru Stasys Jukna " Boolean Function Complexity: Advances and Frontiers ":

Definisi 18.30. Fungsi dengan l < n disebut sebagai generator pseudorandom ( s , ϵ ) aman ( s , ϵ ) jika untuk setiap sirkuit C ukuran s pada n variabel, | P r [ C ( y ) = 1 ] - P r [ C ( G $G : \{0,1\}^l \to \{0,1\}^n$$l < n$$(s,\epsilon)$$C$$s$$n$ mana y dipilih secara seragam secara acak dalam { 0 , 1 } n , dan x dalam { 0 , 1 } l .

$$|Pr[C(y) = 1] − Pr[C(G(x)) = 1]| < \epsilon,$$ $y$$\{0,1\}^n$$x$$\{0,1\}^l$

Definisi 18.31. Biarkan menjadi fungsi boolean. Kita mengatakan bahwa f adalah ( s , ϵ ) -barang jika untuk sirkuit C ukuran s , | P r [ C ( x ) = f ( x ) ] - $f : {0,1}^n \to {0,1}$$f$$(s,\epsilon)$$C$$s$ manaxdipilih secara seragam secara acak dalam{0,1}n.

$$|Pr[C(x) = f(x)] − \frac{1}{2}| < \epsilon,$$ $x$$\{0,1\}^n$

Generator fungsi pseudo-acak adalah fungsi boolean . Dengan mengatur variabel- y secara acak, kita memperoleh subfungsi acaknya f y ( x ) = f ( x , y ) . Biarkan h : { 0 , 1 } n → { 0 , $f(x,y) : \{0,1\}^{n+n^2} \to \{0,1\}$$y$$f_y(x) = f(x,y)$ menjadi fungsi boolean yang benar-benar acak. Sebuah generator f ( x , y ) aman terhadap Γ -attack jika untuk setiap rangkaian C di Γ , | P r [ C ( f y ) = 1 ] - P r [ C ( h ) = 1 ] | < 2 - n 2$h : \{0,1\}^n \to \{0,1\}$$f(x,y)$$\Gamma$$C$$\Gamma$

$$|Pr[C(f_y) = 1] − Pr[C(h) = 1]| < 2^{−n^2}.$$

Sebuah bukti alami terhadap Λ adalah properti Φ : B n → 0 , 1 memenuhi tiga kondisi berikut: 1. Kegunaan terhadap Λ : Φ ( f ) = 1 menyiratkan f ∉ Λ . 2. Kelemahan: Φ ( f ) = 1 untuk setidaknya 2 - O ( n ) fraksi dari semua fungsi 2 2 n f $\Gamma$$\Lambda$$\Phi : B_n \to {0,1}$
$\Lambda$$\Phi(f) = 1$$f \notin \Lambda$
$\Phi(f) = 1$$2^{−O(n)}$$2^{2^n}$ . 3. Konstruktivitas: Φ ∈ Γ , yaitu, ketika dilihat sebagai fungsi boolean dalam N = 2 n variabel, properti Φ sendiri milik kelas Γ . $f \in B_n$
$\Phi \in \Gamma$$N = 2^n$$\Phi$$\Gamma$

Teorema 18.35. Jika kelas kompleksitas berisi generator fungsi pseudo-acak yang aman terhadap serangan Γ, maka tidak ada Γ -bukti alami terhadap Λ .$\Lambda$$\Gamma$$\Lambda$

Pertanyaannya adalah: 1. Apakah kita percaya jika ada fungsi keras seperti itu? 2. Seberapa konstruktif / besar apa yang kita harapkan dari properti pada bukti pemisahan yang mungkin saat ini?

Di sisi lain, Razbarov telah menyebutkan di berbagai tempat bahwa ia secara pribadi memandang hasilnya sebagai panduan untuk apa yang harus dihindari dan bukan sebagai hambatan penting untuk membuktikan batas bawah.

Terlepas dari makalah Ryan Williams selama beberapa tahun terakhir ada dua makalah yang ia sebutkan:

1. $\mathsf{NP}$$\mathsf{P}$

2. $\mathsf{NC^1}$$\mathsf{TC^0}$$\mathsf{TC^0}$

Relativization dan Aljabarisasi sedikit lebih rumit dan tergantung pada cara kita mendefinisikan relaztivization untuk kelas-kelas ini. Tetapi sebagai aturan umum diagonalisasi sederhana (diagonalisasi yang menggunakan contoh tandingan yang sama untuk semua mesin yang menghitung fungsi yang sama, yaitu contoh tandingan hanya bergantung pada mesin apa dalam komputasi yang lebih kecil dan tidak bergantung pada kode mereka dan bagaimana mereka menghitung ) tidak dapat memisahkan kelas-kelas ini.

Dimungkinkan untuk mengekstrak fungsi diagonalisasi yang tidak sederhana dari hasil diagonalisasi tidak langsung seperti batas waktu ruang-batas yang lebih rendah untuk SAT.