Apakah

Sejauh yang saya mengerti, upaya Program teori kompleksitas geometri untuk memisahkan dengan membuktikan bahwa permament dari matriks bernilai kompleks adalah jauh lebih sulit untuk menghitung dari determinan.$VP \neq VNP$

Pertanyaan yang saya miliki setelah membaca sekilas tentang GCT Papers: Apakah ini segera menyiratkan , atau apakah itu hanya langkah besar menuju tujuan ini?$P \neq NP$

Jawaban singkatnya adalah 'tidak'. Tidak ada implikasi seperti itu yang diketahui. Ada dua kendala utama: Beralih dari kompleksitas sirkuit aritmatika ke kompleksitas boolean (VP ≠ VNP menyiratkan P / poli ≠ NP / poli) dan kemudian beralih dari kompleksitas sirkuit boolean (P / poli ≠ NP / poli) ke kompleksitas seragam (P ≠ NP ). Tak satu pun dari langkah-langkah ini diketahui. Saya percaya bahwa P / poly ≠ NP / poly menyiratkan VP ≠ VNP.

Dengan asumsi hipotesis Riemann umum (GRH), koneksi yang cukup kuat berikut ini diketahui antara dan runtuhnya hierarki polinomial ( P $VP= VNP$${\rm PH}$ ):

1. Jika $VP= VNP\,$ (di atas bidang apa pun) maka hierarki polinomial runtuh ke tingkat kedua;
2. Jika $VP=VNP\,$di atas bidang karakteristik , lalu N C 3 / p o l y = P / p o l y = P H / p o l y ;$0$$\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$
3. Jika $VP=VNP\,$di atas bidang dengan karakteristik hingga , maka N C 2 / p o l y = P / p o l y = P H / p o l y .$p$$\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$

Ini adalah hasil dari: Peter Burgisser, " hipotesis Cook versus Valiant ", Theor. Comp. Sci., 235: 71-88, 2000.

Lihat juga: Burgisser, " Kelengkapan dan Pengurangan dalam Teori Kompleksitas Aljabar ", 1998.

Saya dapat memberi Anda alasan tidak resmi mengapa pemisahan itu tidak membuktikan $P \ne NP$ .

VP dan VNP fokus pada fungsi aljabar yang derajatnya dibatasi oleh polinomial. Perhatikan bahwa mudah untuk menghitung dalam fungsi aljabar tingkat eksponensial dengan sirkuit aljabar ukuran polinomial.

Ada pengurangan kedalaman 1 yang diketahui untuk sirkuit aljabar: setiap sirkuit aljabar ukuran polinom yang menghitung polinomial derajat dapat diubah menjadi sirkuit aljabar dengan ukuran polinomial dan kedalaman O ( log d log n ) .$d$$O(\log d \log n)$

Anda mungkin berpikir dari sebagai aljabar varian N C 2 , dengan demikian membuktikan bahwa V P ≠ V N P sebesar membuktikan setara non-seragam aljabar dari N C 2 ≠ # P . Itu tidak akan mengesampingkan P = N P , setidaknya tidak segera.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = NP$

Penafian : Saya tidak dapat mengakses kertas sekarang dan saya tidak ingat apakah pengurangan bekerja di bidang apa pun atau hanya di bidang terbatas.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Perhitungan paralel cepat dari polinomial menggunakan beberapa prosesor . SIAM J. Comput. 12 (4), hlm. 641-644, 1983.