Ist die Primzahlfunktion # P-complete?

Denken Sie daran, dass $\pi(n)$ die Anzahl der Primzahlen $\le n$ die Primzahlfunktion ist . Bei "PRIMES in P" ist die Berechnung von $\pi(n)$ in #P. Ist das Problem # P-vollständig? Oder gibt es vielleicht einen Grund für die Komplexität zu der Annahme, dass dieses Problem nicht # P-vollständig ist?

PS Mir ist klar, dass dies ein bisschen naiv ist, da jemand das Problem untersucht und dies bewiesen / widerlegt / vermutet haben muss, aber ich kann die Antwort nicht in der Literatur finden. Sehen Sie hier, wenn Sie neugierig sind, warum es mich interessiert.

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

@MohsenGhorbani: Nein, nicht die "gleichen" Probleme. Nicht einmal ähnlich.

Igor Pak

Keine Beweise dagegen, nur neugierig: Kennen wir eine einzelne Funktion

, die # P-vollständig ist und n wirklich als Zahl behandelt? Das heißt, wir können immer die Binärdarstellung von n betrachten und diese Binärzeichenfolge als SAT-Formel oder Diagramm behandeln, aber das möchte ich vermeiden.

f (n)

$f(n)$

Joshua Grochow

@JoshuaGrochow Die "natürlichen" (nicht NT) harten Probleme, die ich mit einem Parameter kenne, sind alle in # EXP-c. Ein Beispiel für ein solches Problem: Anzahl der Kacheln von

Quadrat mit einer festen Menge

von Kacheln (dh die Kacheln sind nicht in der Eingabe). Thm: es gibt

st dieses Problem ist # EXP-c.

n \times n

$n \times n$

T

$T$

T

$T$

Igor Pak

@Joshua Dies hängt ziemlich mit der NP-Vollständigkeit von

, für die wir anscheinend noch keine definitive Antwort haben: cstheory.stackexchange.com/questions/14124/…

f (n)

$f(n)$

domotorp

Beachten Sie, dass

, also

seit Miller-Rabin in #P war.

# P^{B P P} = # P

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

π

$\pi$

Emil Jeřábek unterstützt Monica

Antworten:

Einige heuristische Beweise: Nach unserem Kenntnisstand sieht $\pi(n)$ wie eine einfache Funktion aus, die durch zufällige Schwankungen korrigiert wird. Daher würde ich erwarten, dass eine Poly-Time-Maschine mit einem $\pi(n)$ -Orakel nicht stärker ist als eine solche Maschine mit einem zufälligen Orakel, und wenn man ein zufälliges Orakel $X$ schreibt und ein separates zufälliges Orakel $Y$ zu $\mathsf{P}$ hinzufügt , erhält man $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ mit der Wahrscheinlichkeit 1 (hier entspricht $Y$ $\pi(n)$ und $X$ ist ein unabhängiges zufälliges Orakel).

Geoffrey Irving
quelle

Ich finde den letzten Satz irreführend. Während in der Tat

, benötigen wir hier tatsächlich

, und wir wissen nicht, ob dies wahr ist. In der Tat ist dies gleichbedeutend mit

\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 unterstützt Monica

@ EmilJeřábek: Sicher, aber in Bezug auf die Beweise, dass

nicht # P-vollständig ist, wenn man formal zeigen könnte, dass wenn es # P-vollständig ist, dann PP = BPP, würde ich das als ziemlich starken Beweis ansehen # P-Vollständigkeit ...

π (n)

$\pi(n)$

Joshua Grochow

@ JoshuaGrochow Ich bin damit einverstanden. Ich denke einfach nicht, dass das Ergebnis auf

mit zufälligem Orakel relevant ist.

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

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

Emil Jeřábek unterstützt Monica

@ EmilJeřábek: Ja, das ist ein guter Punkt. Würden Sie als Beweis dafür akzeptieren, dass

zwei zufällige Orakel gegeben hat, von denen ich denke, dass wir sie kennen?

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

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

Geoffrey Irving

Wissen wir das?

Emil Jeřábek unterstützt Monica