Konsekuensi #P = FP

Yang akan menjadi konsekuensi dari #P = FP?

Saya tertarik pada konsekuensi praktis dan teoritis.

Dari sudut pandang praktis, saya sangat tertarik pada konsekuensi pada Kecerdasan Buatan.

Pointer ke kertas atau buku lebih dari diterima.

Tolong jangan katakan bahwa #P = FP menyiratkan P = NP, saya sudah tahu itu. Juga, tolong jangan katakan "tidak akan ada konsekuensi praktis jika algoritma berjalan dalam waktu , di mana adalah jumlah elektron di Semesta" $\Omega(n^{\alpha})$ $\alpha$ : ijinkan saya untuk berasumsi bahwa, jika algoritma waktu polinomial deterministik untuk ada masalah # P-complete, waktu menjalankannya adalah "clement" ( , misalnya) $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
sumber

Jawaban:

Berikut adalah beberapa konsekuensi teoretis dari kesetaraan FP = # P, meskipun tidak ada hubungannya dengan kecerdasan buatan. Asumsi FP = # P setara dengan P = PP , jadi izinkan saya menggunakan notasi terakhir.

Jika P = PP, maka kita memiliki P = BQP : perhitungan kuantum polinomial-waktu dapat disimulasikan oleh perhitungan polinomial-waktu klasik dan deterministik. Ini adalah konsekuensi langsung dari BQP⊆PP [ADH97, FR98] (dan dari hasil sebelumnya BQP⊆P ^PP [BV97]). Di atas pengetahuan saya, P = BQP tidak diketahui mengikuti dari asumsi P = NP. Situasi ini berbeda dari kasus perhitungan acak ( BPP ): karena BPP⊆NP ^NP [Lau83], persamaan P = BPP mengikuti dari P = NP.

Konsekuensi lain dari P = PP adalah bahwa model perhitungan Blum-Shub-Smale atas real dengan konstanta rasional sama dengan mesin Turing dalam arti tertentu. Lebih tepatnya, P = PP menyiratkan P = BP (P _ℝ⁰ ); yaitu, jika bahasa L ⊆ {0,1} ^* dapat dipilih oleh program bebas-konstan di atas real dalam waktu polinomial, maka L dapat ditentukan oleh mesin Turing polinomial waktu. (Di sini "BP" adalah singkatan dari "Boolean part" dan tidak ada hubungannya dengan BPP.) Ini mengikuti dari BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. Lihat kertas untuk definisi. Masalah penting dalam BP (P _ℝ⁰ ) adalah masalah jumlah akar kuadratdan kawan-kawan (mis. “Diberikan bilangan bulat k dan satu set titik koordinat bilangan bulat yang terbatas di pesawat, apakah ada pohon spanning dengan panjang total paling banyak k ?”) [Tiw92].

Demikian pula untuk argumen kedua, masalah komputasi bit tertentu dalam x ^y ketika bilangan bulat positif x dan y diberikan dalam biner akan berada dalam P jika P = PP.

Referensi

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen dan Peter Bro Miltersen. Pada kompleksitas analisis numerik. Jurnal SIAM tentang Komputer , 38 (5): 1987–2006, Januari 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais dan Ming-Deh A. Huang. Komputasi kuantum. Jurnal SIAM tentang Komputasi , 26 (5): 1524–1540, Oktober 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein dan Umesh Vazirani. Teori kompleksitas kuantum. Jurnal SIAM tentang Komputasi , 26 (5): 1411–1473, Oktober 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow dan John Rogers. Keterbatasan kompleksitas pada perhitungan kuantum. Jurnal Ilmu Komputer dan Sistem , 59 (2): 240–252, Oktober 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP dan hierarki waktu polinomial. Information Processing Letters , 17 (4): 215–217, November 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Masalah yang lebih mudah diselesaikan pada RAM aljabar unit-cost. Journal of Complexity , 8 (4): 393–397, Desember 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
sumber

Anda mengalahkan saya untuk ini! Sebenarnya, Anda benar tentang BQP vs NP. Tampaknya ada bukti yang masuk akal bahwa BQP tidak terkandung dalam PH (lihat misalnya arxiv.org/abs/0910.4698 ), meskipun saya percaya dugaan Generalized Linial-Nisan yang digunakan pada bit kedua sejak itu terbukti salah.

Joe Fitzsimons

@turkistany: Jika saya tidak salah, P = NP menyiratkan P = BPP karena BPP terkandung dalam PH, dan jika P = NP maka P = PH.

Niel de Beaudrap

Kebetulan: +1 untuk (FP = # P) ⇔ (P = PP), bahkan menyisihkan seluruh isi jawaban.

Niel de Beaudrap

@ Jo: Sehubungan dengan jawaban atas pertanyaan lain, saya berpikir bahwa bukti terbaik “P = NP tidak menyiratkan P = BQP” tanpa benar-benar membuktikan P = NP ≠ BQP mungkin akan menjadi hasil pemisahan oracle: “Ada sebuah oracle A sehingga P ^ A = NP ^ A ≠ BQP ^ A. ”Tentu saja, ini tidak mudah sama sekali karena hasil itu akan menyiratkan BQP ^ A⊈PH ^ A, menyelesaikan pertanyaan terbuka besar.

Tsuyoshi Ito

@ Tsuyoshi: Tidak bisakah Anda membuat oracle seperti itu dari oracle mana pun yang BQP tidak terkandung dalam PH, hanya dengan membawanya bersama-sama dengan PH untuk membentuk oracle baru?

Joe Fitzsimons

Dalam model grafis , banyak masalah estimasi # P-complete, karena mereka melibatkan melakukan perhitungan jumlah-produk a la permanen daripada grafik umum. Jika #P = FP, maka model grafis tiba-tiba menjadi jauh lebih mudah, dan kita tidak perlu berkutat dengan model rendah-treewidth lagi.

Suresh Venkat
sumber

$PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Mohammad Al-Turkistany
sumber

Dapatkah seseorang mengklarifikasi: apakah ini tidak sama dengan mengatakan "P = PH" (yang akan segera mengikuti dari P = NP)?

Niel de Beaudrap

@Niel: Ini tidak sama, itu lebih kuat.

Giorgio Camerani

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

@ Semua: hanya untuk mengklarifikasi --- komentar pertama saya di atas adalah menanyakan pertanyaan berikut "Apakah jawaban turkistani setara dengan pernyataan bahwa FP = # P menyiratkan P = PH?" Jika saya ingin tahu apakah FP = # P setara dengan P = PH, saya akan menanyakan ini dalam komentar di posting asli, bukan pada jawaban turkistany.

Niel de Beaudrap

@Niel: Anda benar. Ini sama dengan mengatakan P = PH, yang mengikuti dari P = NP. Oleh karena itu penggunaan teorema Toda tidak diperlukan, karena FP = #P sudah menyiratkan P = NP = PH.

Robin Kothari