<p>Is there evidence that <span class="math-container">$\oplus P\subseteq\#P$</span> and evidence towards <span class="math-container">$\oplus P\not\subseteq\#P$</span> ? We know <span class="math-container">$\oplus P\subseteq FP^{\#P}$</span></p>
<p>What are some barriers to proving this inclusion <span class="math-container">$\oplus P\subseteq\#P$</span>?</p>

CC BY-SA 4.0
2024-04-02T23:28:17.383Z
If $\mathsf{\oplus P} \subseteq \mathsf{\# P}$, then $\mathsf{\oplus P} \subseteq \mathsf{UP}$, and then (by Valiant-Vazirani) $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{UP}}$, which is getting close to $\mathsf{NP} \subseteq \mathsf{UP}$. Now, we don't know bad consequences of the latter, but it seems unlikely...
Joshua Grochow
CC BY-SA 4.0
2024-04-02T23:32:46.343Z
@JoshuaGrochow 1. If we assume $\#P\subseteq PHCF\subseteq\oplus P=FCH=FP^{\#P}$ does it make $\oplus P\subseteq\#P$ any more plausible (like do barriers get ameliorated)?
Turbo
CC BY-SA 4.0
2024-04-02T23:36:29.153Z
2. If $\#P\subseteq\oplus P$, is there any consequence? I do not see anything other than counting hierarchy collapsing.
Turbo
CC BY-SA 4.0
2024-04-03T06:35:36.070Z
@JoshuaGrochow Since $UL=NL$ is believed, is it any more likely that $\oplus L\subseteq\# L$ holds?
Turbo
CC BY-SA 4.0
2024-04-03T06:45:06.910Z
Note also $PL^{PL}=PL$. So there is no obstruction to $\# L\subseteq\oplus L$ since counting hierarchy collapses anyway in Logspace related counting classes.
Turbo
CC BY-SA 4.0
2024-04-03T14:12:55.997Z
What is $\oplus P\subseteq\#P$ supposed to mean? $\oplus P$ is a class of languages, whereas $\#P$ is a class of functions.
Emil Jeřábek
CC BY-SA 4.0
2024-04-03T15:28:47.133Z
I can write $F\oplus P$ but it is the same.
Turbo
CC BY-SA 4.0
2024-04-03T16:55:37.943Z
What is $F\oplus P$, and what is the same as what?
Emil Jeřábek
CC BY-SA 4.0
2024-04-03T17:37:31.467Z
Function ParityP. Symbolically they just use $\oplus P$ for both function and language classes for parityP.
Turbo
CC BY-SA 4.0
2024-04-04T00:32:06.580Z
@EmilJeřábek Parity-P says Yes or No whereas F-Parity outputs 1 or 0
Tayfun Pay
CC BY-SA 4.0
2024-04-04T07:44:35.093Z
@Tay Really? That’s even more confusing than before. So what is the exact definition used here? Does $F{\oplus}P$ consist only of 0–1 characteristic functions of $\oplus P$ predicates, or does it contain all functions of polynomially bounded length whose bitgraph is computable in $\oplus P$? This needs to be clearly defined. I initially read the question here with the 0–1 interpretation in mind, and Josh’s comment is consistent with it, but then Turbo started making wild claims about $\#P\subseteq\oplus P$ in another question, and this requires functions of arbitrary polynomial-length growth.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T08:17:50.710Z
The most natural usage of the notation would be that as a function class, $\oplus\mathrm P$ stands for the class of characteristic functions of $\oplus\mathrm P$ predicates, whereas $\mathrm{F{\oplus}P}$ is the class of polynomially bounded functions with $\oplus\mathrm P$ bit-graph, which actually coincides with $\mathrm{FP^{\oplus P}}$. Thus $\oplus\mathrm P$ is the class of 0–1 valued functions in $\mathrm{F{\oplus}P}$. But this is clearly inconsistent with Turbo's usage.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T08:25:39.223Z
Btw, I assumed that the "PHCF" above was a typo for something, but it turns out to come from an old paper by Wagner, where he uses "CPH" to denote CH, and "PHCF" to denote FCH.
Emil Jeřábek
CC BY-SA 4.0
2024-04-04T14:06:28.283Z
@EmilJeřábek Thank you. I will remove my question and repost.
Turbo
<cc.complexity-theory><complexity-classes><counting-complexity><big-picture><barriers>
Evidence for $\oplus P\subseteq\#P$ and barriers to proving it
Turbo
# Evidence for $\oplus P\subseteq\#P$ and barriers to proving it

(Asked by: username_0 on 2024-04-02)

Is there evidence that $\oplus P\subseteq\#P$ and evidence towards $\oplus P\not\subseteq\#P$ ? We know $\oplus P\subseteq FP^{\#P}$

What are some barriers to proving this inclusion $\oplus P\subseteq\#P$?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, big-picture, barriers
> **Comments:**
> **username_1**: If $\mathsf{\oplus P} \subseteq \mathsf{\# P}$, then $\mathsf{\oplus P} \subseteq \mathsf{UP}$, and then (by Valiant-Vazirani) $\mathsf{NP} \subseteq \mathsf{BPP}^{\mathsf{UP}}$, which is getting close to $\mathsf{NP} \subseteq \mathsf{UP}$. Now, we don't know bad consequences of the latter, but it seems unlikely...  
> **username_0**: @JoshuaGrochow 1. If we assume $\#P\subseteq PHCF\subseteq\oplus P=FCH=FP^{\#P}$ does it make $\oplus P\subseteq\#P$ any more plausible (like do barriers get ameliorated)?  
> **username_0**: 2. If $\#P\subseteq\oplus P$, is there any consequence? I do not see anything other than counting hierarchy collapsing.  
> **username_0**: @JoshuaGrochow Since $UL=NL$ is believed, is it any more likely that $\oplus L\subseteq\# L$ holds?  
> **username_0**: Note also $PL^{PL}=PL$. So there is no obstruction to $\# L\subseteq\oplus L$ since counting hierarchy collapses anyway in Logspace related counting classes.  
> **username_2**: What is $\oplus P\subseteq\#P$ supposed to mean? $\oplus P$ is a class of languages, whereas $\#P$ is a class of functions.  
> **username_0**: I can write $F\oplus P$ but it is the same.  
> **username_2**: What is $F\oplus P$, and what is the same as what?  
> **username_0**: Function ParityP. Symbolically they just use $\oplus P$ for both function and language classes for parityP.  
> **username_3**: @EmilJeřábek Parity-P says Yes or No whereas F-Parity outputs 1 or 0  
> **username_2**: @Tay Really? That’s even more confusing than before. So what is the exact definition used here? Does $F{\oplus}P$ consist only of 0–1 characteristic functions of $\oplus P$ predicates, or does it contain all functions of polynomially bounded length whose bitgraph is computable in $\oplus P$? This needs to be clearly defined. I initially read the question here with the 0–1 interpretation in mind, and Josh’s comment is consistent with it, but then Turbo started making wild claims about $\#P\subseteq\oplus P$ in another question, and this requires functions of arbitrary polynomial-length growth.  
> **username_2**: The most natural usage of the notation would be that as a function class, $\oplus\mathrm P$ stands for the class of characteristic functions of $\oplus\mathrm P$ predicates, whereas $\mathrm{F{\oplus}P}$ is the class of polynomially bounded functions with $\oplus\mathrm P$ bit-graph, which actually coincides with $\mathrm{FP^{\oplus P}}$. Thus $\oplus\mathrm P$ is the class of 0–1 valued functions in $\mathrm{F{\oplus}P}$. But this is clearly inconsistent with Turbo's usage.  
> **username_2**: Btw, I assumed that the "PHCF" above was a typo for something, but it turns out to come from an old paper by Wagner, where he uses "CPH" to denote CH, and "PHCF" to denote FCH.  
> **username_0**: @EmilJeřábek Thank you. I will remove my question and repost.  

---

## 0 answers

