Apakah fungsi penghitungan prime # P-selesai?

Ingat jumlah bilangan prima adalah fungsi penghitungan utama . Dengan "PRIMES dalam P", komputasi ada di #P. Apakah masalahnya # P-selesai? Atau, mungkin, ada alasan kerumitan untuk percaya bahwa masalah ini bukan # P-complete? $\pi(n)$ $\le n$ $\pi(n)$

PS Saya menyadari ini agak naif karena seseorang pasti telah mempelajari masalahnya dan membuktikan / membantah / menduga hal ini, tetapi sepertinya saya tidak dapat menemukan jawabannya dalam literatur. Lihat di sini jika Anda penasaran mengapa saya peduli.

cc.complexity-theory counting-complexity nt.number-theory comp-number-theory primes Igor Pak
sumber

@MohsenGhorbani: Tidak, bukan masalah yang "sama". Bahkan tidak mirip.

Igor Pak

Bukan bukti yang menentang, hanya ingin tahu: apakah kita tahu fungsi tunggal yaitu # P-complete yang benar-benar memperlakukan n sebagai angka? Yaitu, kita selalu dapat melihat representasi biner dari n dan memperlakukan string biner itu sebagai rumus atau grafik SAT, tetapi saya ingin menghindarinya.

f (n)

$f(n)$

Joshua Grochow

@ JoshuaGrochow Masalah keras "alami" (bukan NT) yang saya tahu dengan satu parameter semuanya di # EXP-c. Contoh dari masalah seperti itu: jumlah tilings kuadrat dengan set ubin tetap (yaitu ubin tidak di input). Thm: terdapat st masalah ini adalah # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Igor Pak

@ Yosua Ini sangat terkait dengan kelengkapan NP dari , yang, tampaknya, kami juga belum memiliki jawaban pasti: cstheory.stackexchange.com/questions/14124/…

f (n)

$f(n)$

domotorp

Perhatikan bahwa , maka berada di #P sejak Miller – Rabin.

# P^{B P P} = # P

$\mathrm{\#P^{BPP}=\#P}$

π

$\pi$

Emil Jeřábek mendukung Monica

Jawaban:

Beberapa bukti heuristik: sepengetahuan kami tampak seperti fungsi sederhana yang dikoreksi oleh fluktuasi acak. Jadi saya berharap mesin poly-time dengan oracle tidak lebih kuat dari mesin dengan oracle acak, dan wrt random oracle menambahkan oracle acak terpisah ke memberikan dengan probabilitas 1 (di sini terkait dengan dan adalah oracle acak independen). $\pi(n)$ $\pi(n)$ $X$ $Y$ $\mathsf{P}$ $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ $Y$ $\pi(n)$ $X$

Geoffrey Irving
sumber

Saya menemukan kalimat terakhir menyesatkan. Meskipun memang , yang sebenarnya kita butuhkan di sini adalah , dan kami tidak tahu apakah ini benar. Bahkan, ini setara dengan .

\underset{X}{Pr} [{P P}^{X} \neq P^{X}] = 1

$\Pr_X[\mathrm{PP}^X\ne\mathrm{P}^X]=1$

\underset{X}{Pr} [P P ⊈ P^{X}] = 1

$\Pr_X[\mathrm{PP}\nsubseteq\mathrm{P}^X]=1$

P P \neq B P P

$\mathrm{PP\ne BPP}$

Emil Jeřábek mendukung Monica

@ EmilJeřábek: Tentu, tetapi dalam hal bukti bahwa tidak # P-selesai, jika seseorang dapat menunjukkan secara formal bahwa jika itu # P-selesai maka PP = BPP, saya akan menganggap itu sebagai bukti yang cukup kuat terhadap # P-kelengkapan ...

π (n)

$\pi(n)$

Joshua Grochow

@ JoshuaGrochow Saya setuju dengan itu. Saya hanya tidak berpikir hasil pada dengan random oracle relevan.

P^{X} \neq {P P}^{X}

$\mathrm P^X\ne\mathrm{PP}^X$

Emil Jeřábek mendukung Monica

@ EmilJeřábek: Ya, itu poin yang bagus. Sebelum saya mengedit, apakah Anda menerima fakta bahwa diberikan dua nubuat acak, yang saya pikir kita tahu?

P^{X Y} \neq # P^{X}

$P^{XY} \ne \#P^X$

Geoffrey Irving

Apakah kita tahu itu?

Emil Jeřábek mendukung Monica