Apa kompleksitas penghitungan jumlah solusi dari masalah P-Space Complete? Bagaimana dengan kelas kompleksitas yang lebih tinggi?

Anda banyak bertanya dalam satu pertanyaan!

#PSPACE sama dengan kelas fungsi yang dapat dihitung dalam ruang polinomial (FPSPACE).

@ Tsuyoshi Ini benar. Namun, sebagian besar pertanyaan yang diajukan jika tidak semua, dapat diulang sebagai pertanyaan umum tunggal: Apakah ada penghitungan kelas untuk kelas lebih tinggi dari (seperti yang dapat dicatat dalam definisi # ) dan apakah hasil yang diketahui berlaku? $NP$$P$

@ Payayfun Bayar: Saya tidak sepenuhnya yakin apa yang Anda maksud untuk kelas deterministik seperti PSPACE, EXP, EXPSPACE. Gagasan "jumlah solusi" biasanya terkait erat dengan nondeterminisme - sejak saat itu Anda dapat bertanya tentang jumlah jalur penerimaan - atau penjumlahan / proyeksi eksistensial. Dalam kasus PSPACE tentu saja Anda dapat menggunakan definisi bilangan kuantifikasi bolak-balik - tetapi kemudian Anda harus menentukan bilangan mana yang ingin Anda hitung - atau fakta bahwa NPSPACE = PSPACE.

Seperti yang disebutkan beberapa komentar, tidak sepenuhnya jelas apa yang ingin Anda maksud untuk #PSPACE. Taruhan terbaik adalah dengan mengambil analog padded-up dari #L yang dipelajari dengan baik. Karena #L terkandung dalam DSPACE (log ^ 2 n), ini akan menyiratkan bahwa # PSPACE = PSPACE, seperti yang disebutkan @TsuyoshiIto di atas. (Di sini saya mengabaikan perbedaan formal yang tidak material antara masalah dan fungsi keputusan.)

Bukankah ini dicakup oleh komentar Tsuyoshi dan Noam di atas?

Apakah ini yang Anda maksud sebenarnya? Jika #P = #PSPACE, bukankah ini menyiratkan bahwa PSPACE P ? Saya tidak percaya ini diketahui. # $\subseteq$$^{\#\mathrm{P}}$

@ PeterShor Saya cukup yakin Daniel berarti ini mathoverflow.net/a/12608/35733 . Tapi tebakan saya (yang belum diverifikasi) adalah bahwa masalah # PSPACE-complete adalah menghitung jumlah penugasan yang memuaskan dari QBF tetap, tidak menghitung jumlah kuantifikasi yang memuaskan dari CNF yang diberikan.

Tidak, saya maksudkan bahwa jumlah kuantifikasi valid dari cnf yang diberikan sama dengan jumlah penugasan cnf yang memuaskan, dengan urutan variabel yang tetap. Sangat menarik karena mengubah urutan variabel mengubah qbfs yang valid, tetapi bukan jumlah total qbfs yang valid.