Ist #P unter Potenzierung geschlossen? Modulo?

7

Die Komplexitätsklasse ist definiert als#P

#P={f polynomial-time NTM M x.f(x)=#acceptM(x)} .

Es ist bekannt, dass unter Addition, Multiplikation und Binomialkoeffizient geschlossen wird. Ich habe mich gefragt, ob es unter Strom geschlossen ist. Zum Beispiel erhalten wir eine Funktion und eine andere Funktion . Stimmt es, dass oder auch Funktionen sind? #P#Pf#Pgfggf#P

Dies wird bearbeitet, nachdem die Frage beantwortet wurde.

Ist ( modulo ) eine Funktion? Wie wäre es, wenn wir gegeben eine - Funktion . dann ( modulo ) eine Funktion?fg#PFPhfh#P


quelle

Antworten:

7

Nein. Nehmen Sie als Gegenbeispiel .f(n)=g(n)=2n

Tsuyoshi Ito
quelle
2
@Geekster: Es ist eine schlechte Form, eine Frage zu erweitern, nachdem Antworten hinzugefügt (und sogar akzeptiert) wurden. Bitte erwägen Sie, eine neue Frage für Ihr neues Problem hinzuzufügen.
Raphael