<p>Are there any known <span class="math-container">$P^{\#P}$</span> complete problems?</p>
<p>The problem would have to be at least as hard as anything in the polynomial hierarchy, but perhaps not as hard as PSPACE</p>

CC BY-SA 4.0
2024-05-23T18:24:26.267Z
For example, one such complete problem is given in https://cstheory.stackexchange.com/a/53032 (NB $\mathrm{P^{PP}=P^{\#P}}$).
Emil Jeřábek
CC BY-SA 4.0
2024-05-24T17:08:37.767Z
@EmilJeřábek What is NB?
Tayfun Pay
CC BY-SA 4.0
2024-05-24T17:29:08.737Z
https://en.wiktionary.org/wiki/NB#Phrase
Emil Jeřábek
CC BY-SA 4.0
2024-05-27T18:30:14.430Z
I have never heard of it in my life before. I thought you were doing some type of a dot notation and had forgotten the . or something. Ok
Tayfun Pay
CC BY-SA 4.0
2024-05-27T18:33:46.033Z
@EmilJeřábek Isn't it actually $P^{PP}$$=$$P^{\#P[1]}$ ?
Tayfun Pay
CC BY-SA 4.0
2024-05-27T19:19:15.623Z
No. ${}{}{}{}{}$
Emil Jeřábek
CC BY-SA 4.0
2024-05-28T21:45:40.477Z
@EmilJeřábek I just checked the BBS86 paper and it does seem like only one call is sufficient to the D#P from a base machine. I also vaguely remember discussing it with someone many years ago... Who knows, I might be missing something. Ok.
Tayfun Pay
CC BY-SA 4.0
2024-05-29T05:46:21.153Z
@TayfunPay What is “BBS86”? In any case, $P^{PP}$ is closed under poly-time Turing reductions. So if $P^{PP}=P^{\#P[1]}$, then $P^{PP}=P^{P^{\#P[1]}}=P^{\#P}$ anyway, as I was saying (but of course, it is trivial to verify this directly). So you are, in effect, claiming that both $P^{PP}=P^{\#P}$ *and* $P^{\#P}=P^{\#P[1]}$.
Emil Jeřábek
CC BY-SA 4.0
2024-05-29T06:12:22.987Z
@TayfunPay There is a [BBS86] reference in the Complexity Zoo (Balcázar, Book, Schöning, *Sparse sets, lowness, and highness*), but as far as I can see, it does not mention #P or PP, or indeed any class outside the polynomial hierarchy. Note also that the Zoo includes separate entries for the classes $\mathrm{P^{\#P}}$ and $\mathrm{P^{\#P[1]}}$ (noting that $\mathrm{P^{PP}=P^{\#P}}$), so if your claim is true, it is apparently unknown to the general public.
Emil Jeřábek
CC BY-SA 4.0
2024-05-29T09:44:47.237Z
@TayfunPay Cai and Hemachandra, *Enumerative counting is hard*, explicitly state $P^{\#P}=P^{\#P[1]}$ as an open problem right after proving various related results (non-adaptive/truth-table reductions to $\#P$ oracles collapse to one call, and we have $X^{\#P}=X^{\#P[1]}$ [or even $X^{\#P}=X^{C_=P[1]}$, I observe] for various oracle classes $X$ based on counting accepting paths of nondeteministic machines, such as UP, NP, or PP).
Emil Jeřábek
CC BY-SA 4.0
2024-05-29T14:39:12.680Z
@TayfunPay Oh, *now* I know which paper you meant (same authors, different title): Balcázar, Book, Schöning, *The polynomial-time hierarchy and sparse oracles*. But the argument they give in Theorem A3 is just the standard trivial observation that $\mathrm{P^{PP}\subseteq P^{\#P}}$ because each call to a PP oracle can be simulated by a call to a #P oracle and checking the highest-order bit of the result. It does not in any way imply or suggest that *polynomially many* calls to a PP oracle could be simulated by a *single* call to a #P oracle. So I still have no idea what you are thinking.
Emil Jeřábek
CC BY-SA 4.0
2024-05-29T16:06:36.263Z
@EmilJeřábek ok. I do know that $P^{\#P[1]} = P^{\#P}$ is an open problem. I think the misinterpretation on my part arose because I just cannot conceive an instance where you would need more than one call to a #P oracle to recognize some language decided by                                                                          $P^{PP}$. After all, even $PH \subseteq P^{\#P[1]}$.... In any case, it has been a while I pondered about these things. My memory is most likely distorted. Ok
Tayfun Pay
CC BY-SA 4.0
2024-05-31T10:37:11.547Z
Thanks, now I understand that problem there. And how this site works. I had searched for `P^PP`, but one has to search for `"P^PP"`. And there is [another candidate](https://cstheory.stackexchange.com/questions/52192/problems-in-ppp)
BeniBela
CC BY-SA 4.0
2024-05-31T10:37:17.137Z
But I could not reduce it to my problem. Perhaps it is too hard and I need something smaller than $P^{#P}$. 
Are there $L^{PP}$-complete problems? Or $ALOGTIME^{PP}$-complete ones? However, it could not even compute the input for the oracle in ALOGTIME. Could you define an oracle call where the oracle gets a pointer to the original input rather than a copy of it?
BeniBela
<cc.complexity-theory><counting-complexity>
$P^{\#P}$ complete problems
BeniBela
# $P^{\#P}$ complete problems

(Asked by: username_0 on 2024-05-23)

Are there any known $P^{\#P}$ complete problems?

The problem would have to be at least as hard as anything in the polynomial hierarchy, but perhaps not as hard as PSPACE

**Tags:** cc.complexity-theory, counting-complexity

> **Comments:**
> **username_1**: For example, one such complete problem is given in https://cstheory.stackexchange.com/a/53032 (NB $\mathrm{P^{PP}=P^{\#P}}$).  
> **username_2**: @EmilJeřábek What is NB?  
> **username_1**: https://en.wiktionary.org/wiki/NB#Phrase  
> **username_2**: I have never heard of it in my life before. I thought you were doing some type of a dot notation and had forgotten the . or something. Ok  
> **username_2**: @EmilJeřábek Isn't it actually $P^{PP}$$=$$P^{\#P[1]}$ ?  
> **username_1**: No. ${}{}{}{}{}$  
> **username_2**: @EmilJeřábek I just checked the BBS86 paper and it does seem like only one call is sufficient to the D#P from a base machine. I also vaguely remember discussing it with someone many years ago... Who knows, I might be missing something. Ok.  
> **username_1**: @TayfunPay What is “BBS86”? In any case, $P^{PP}$ is closed under poly-time Turing reductions. So if $P^{PP}=P^{\#P[1]}$, then $P^{PP}=P^{P^{\#P[1]}}=P^{\#P}$ anyway, as I was saying (but of course, it is trivial to verify this directly). So you are, in effect, claiming that both $P^{PP}=P^{\#P}$ *and* $P^{\#P}=P^{\#P[1]}$.  
> **username_1**: @TayfunPay There is a [BBS86] reference in the Complexity Zoo (Balcázar, Book, Schöning, *Sparse sets, lowness, and highness*), but as far as I can see, it does not mention #P or PP, or indeed any class outside the polynomial hierarchy. Note also that the Zoo includes separate entries for the classes $\mathrm{P^{\#P}}$ and $\mathrm{P^{\#P[1]}}$ (noting that $\mathrm{P^{PP}=P^{\#P}}$), so if your claim is true, it is apparently unknown to the general public.  
> **username_1**: @TayfunPay Cai and Hemachandra, *Enumerative counting is hard*, explicitly state $P^{\#P}=P^{\#P[1]}$ as an open problem right after proving various related results (non-adaptive/truth-table reductions to $\#P$ oracles collapse to one call, and we have $X^{\#P}=X^{\#P[1]}$ [or even $X^{\#P}=X^{C_=P[1]}$, I observe] for various oracle classes $X$ based on counting accepting paths of nondeteministic machines, such as UP, NP, or PP).  
> **username_1**: @TayfunPay Oh, *now* I know which paper you meant (same authors, different title): Balcázar, Book, Schöning, *The polynomial-time hierarchy and sparse oracles*. But the argument they give in Theorem A3 is just the standard trivial observation that $\mathrm{P^{PP}\subseteq P^{\#P}}$ because each call to a PP oracle can be simulated by a call to a #P oracle and checking the highest-order bit of the result. It does not in any way imply or suggest that *polynomially many* calls to a PP oracle could be simulated by a *single* call to a #P oracle. So I still have no idea what you are thinking.  
> **username_2**: @EmilJeřábek ok. I do know that $P^{\#P[1]} = P^{\#P}$ is an open problem. I think the misinterpretation on my part arose because I just cannot conceive an instance where you would need more than one call to a #P oracle to recognize some language decided by                                                                          $P^{PP}$. After all, even $PH \subseteq P^{\#P[1]}$.... In any case, it has been a while I pondered about these things. My memory is most likely distorted. Ok  
> **username_0**: Thanks, now I understand that problem there. And how this site works. I had searched for `P^PP`, but one has to search for `"P^PP"`. And there is [another candidate](https://cstheory.stackexchange.com/questions/52192/problems-in-ppp)  
> **username_0**: But I could not reduce it to my problem. Perhaps it is too hard and I need something smaller than $P^{#P}$.  Are there $L^{PP}$-complete problems? Or $ALOGTIME^{PP}$-complete ones? However, it could not even compute the input for the oracle in ALOGTIME. Could you define an oracle call where the oracle gets a pointer to the original input rather than a copy of it?  

---

## 0 answers

