<p>First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq PPAD}$. Thus, if we assume
$$\mathrm{\#P\subseteq PPAD},$$
then
$$\mathrm{\#P^{PPAD}\subseteq PPAD},$$
which by induction implies
$$\mathrm{FCH=PPAD}.$$
Passing to decision problems, since $\mathrm{P^{PPAD}\subseteq P^{TFNP}\subseteq NP\cap coNP}$, this shows
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP}.$$
(Note that using the closure of $\mathrm{PPAD}$ under Turing reductions, $\mathrm{P^{PPAD}}$ consists of predicates whose characteristic functions can be computed as projections of $\mathrm{PPAD}$ problems.)</p>

<p>As for $\oplus\mathrm P$, I believe $\mathrm{PPA\supseteq PPAD}$ can be solved by binary search on the predicate “the sum of degrees of vertices whose labels start with a given string is odd”, which means
$$\mathrm{PPAD\subseteq FP^{\oplus P}},$$
thus (using $\mathrm{P^{\oplus P}=\oplus P}$)
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP=\oplus P}.$$
A similar argument applies with $\mathrm{Mod}_p\mathrm P$ in place of $\oplus\mathrm P$ for any prime $p$.</p>

<p>I don’t know about UP.</p>

CC BY-SA 3.0
2017-08-01T10:54:34.427Z
is it believed $Mod_pP\subseteq P/poly$ possible at $p\neq 2$?
Turbo
CC BY-SA 3.0
2017-08-01T13:28:36.027Z
It’s possible in the sense that we don’t know how to disprove it at the moment. However, it is quite unlikely, just like for $\oplus P$. To begin with, it would imply $\mathrm{PH\subseteq P/poly}$ by Toda’s theorem.
Emil Jeřábek
CC BY-SA 3.0
2017-08-04T00:35:39.360Z
( ͡° ͜ʖ ͡°) .....
Daniel Apon
CC BY-SA 3.0
2017-11-29T03:56:01.963Z
@EmilJeřábek Does
$$PP ⊆ coNP^{TFNP}⟹CH=PH=\Sigma_2∩\Pi_2=PP=\oplus P=coNP^{TFNP}∩NP^{TFNP}$$ hold? Essentially asking instead of $PPAD$ we assume $TFNP$ Oracle and/or instead of $P^{TFNP}$ we assume $(\Pi_i^P)^{TFNP}$ or $(\Sigma_i^P)^{TFNP}$ in polynomial hierarchy such as $(\Pi_2^P)^{TFNP}=(coNP)^{TFNP}$ can we expect similar collapse as in your answer to query?
Turbo
CC BY-SA 3.0
2017-11-29T09:50:10.587Z
The inclusion of PP in any subclass $C$ of ModPH collapses CH to $P^C$. However, you won’t get $PP=\oplus P$ that way, this relied on the connection of PPAD to parity.
Emil Jeřábek
CC BY-SA 3.0
2017-12-02T10:01:29.557Z
@EmilJeřábek $\Sigma_i^P=\Pi_i^P=PH=PP=CH\implies\#\Sigma_{i-1}^P=\#\Sigma_{i}^P$ plausible? Would this give $U\Sigma_i^P=\Sigma_i^P=\Pi_i^P$ (theorem $61$ in Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra, Mathematics Workshop, Kaikoura, January 7-15, $2000$) (De Gruyter Series in Logic and Its Applications, 4) edited Rod G. Downey, Denis Roman Hirschfeldt). Here by $U\Sigma_i^P$ I mean the appropriate class in UAP (I think there should be such a class (where every alternation has unique accepting path) but not sure).
Turbo
CC BY-SA 4.0
2021-08-30T09:46:16.907Z
@EmilJeřábek If $PP$ is in $Mod_kP$ at a $k>2$ (say $k=15$) and odd would it follow $PP$ is in $\oplus P$?
Turbo
CC BY-SA 4.0
2023-05-19T07:27:53.107Z
I have frankly no idea what you are talking about. What is $\mathrm{FL^{SpanL}}$, where does your "we know" come from, and why on earth should it imply anything about FCH or PPAD?
Emil Jeřábek
CC BY-SA 4.0
2023-05-19T14:37:41.383Z
@EmilJeřábek Sorry for not being clear. I was talking in the context of the question above and your answer. I think $\#P\subseteq FL^{SpanL}$ comes from https://www.sciencedirect.com/science/article/pii/030439759390252O (theorem 4.8). Then in the context of this question we seem to get $FCH=PPAD=FL^{SpanL}$ correct? Does it also give $\#P=SpanL$?
Turbo
CC BY-SA 4.0
2023-05-19T17:26:10.093Z
I see. Yes, the assumption also implies $\mathrm{FCH=FL^{SpanL}}$. I see no reason it should collapse anything down to SpanL.
Emil Jeřábek
CC BY-SA 4.0
2023-05-19T21:52:58.727Z
@EmilJeřábek This was my thought. Please correct me if I am wrong. The way theorem $4.8$ works in that paper (I think) is first show given a Boolean function f in form of $3CNF$, the number of non-satisfying assignments is in $SpanL$. We subtract $2^n$ and this quantity in $Logspace$. ....
Turbo
CC BY-SA 4.0
2023-05-19T21:53:04.767Z
...Now I am wondering if $CH=NP=coNP$ as in the answer to the posted question above holds, then given a $3CNF$ $f_1$ can we construct (in Logspace) another $3CNF$ $f_2$ such that the number of satisfying assignments in $f_1$ is the number of non-satisfying assignments in $f_2$? If we can do that then we don't have to subtract and directly get number of satisfying assignments by output of the $SpanL$ machine placing $\#P$ in $SpanL$.
Turbo
CC BY-SA 4.0
2023-05-20T08:02:30.410Z
NP = coNP implies there is a Logspace transformation of a 3CNF $f_1$ to a 3CNF $f_2$ such that $f_2$ is satisfiable iff $f_1$ is unsatisfiable. However, this is far from changing the number of satisfying assignments the way you want. In fact, what you write is impossible even disregarding the Logspace requirement because the numbers of satisfying assignments of 3CNF obey  strict constraints that are not symmetric: to begin with, the number of satisfying assignments of a 3CNF in $n$ variables is either $2^n$ or at most $7\cdot2^{n-3}$. Thus, if $f_1$ has a nonzero but small number of ...
Emil Jeřábek
CC BY-SA 4.0
2023-05-20T08:03:09.560Z
... satisfying assignments, then no such $f_2$ exists.
Emil Jeřábek
CC BY-SA 4.0
2023-05-20T11:40:05.333Z
@EmilJeřábek I see OK. One last attempt. If $CH=NP$ or $CH=UP$ then to show $\#P=SpanL$ we only need to show $FNP=SpanL$ or $FUP=SpanL$ respectively right? Are these possible if $CH=NP$ or $CH=UP$ respectively?
Turbo
CC BY-SA 4.0
2023-05-20T16:55:06.503Z
I see no reason this should hold.
Emil Jeřábek
CC BY-SA 4.0
2023-05-22T22:06:58.697Z
@EmilJeřábek I found one more thing. $UP=NP\iff SpanP=\#P$ holds. So in fact $\#L\subseteq SpanL\subseteq FL^{coUP}=FL^{UP}=\#P=SpanP=CH\subseteq FL^{SpanL}\subseteq FL^{UP}=FL^{coUP}$ holds according to your answer (I think). I do not know what this implies if say we assume $FUL=FNL=FPL=F\oplus L=\#L$ as well ($UL=NL$ is believed to be true). From the proof of the paper it seems $FL^{UP}\subseteq FL^{SpanL}$ holds. So I think

$\#L\subseteq SpanL\subseteq FL^{coUP}=FL^{UP}=\#P=SpanP=CH\subseteq FL^{SpanL}=FL^{UP}=FL^{coUP}$ might be true.
Turbo
CC BY-SA 3.0
2017-07-31T13:51:08.627Z
2017-07-31T13:51:08.627Z
Emil Jeřábek
<p>We know <span class="math-container">$\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$</span> and the polynomial hierarchy collapses (<span class="math-container">$FP^{PPAD}=PPAD$</span> following Emil Jerabek's comment).</p>
<blockquote>
<ol>
<li><p>Can <span class="math-container">$\#P\subseteq {PPAD}$</span> give a stronger collapse such as <span class="math-container">$\oplus P=UP=NP=coNP=PP$</span> or <span class="math-container">$NP=coNP=P^{PPAD}$</span>?</p>
</li>
<li><p>What other consequences follow in <span class="math-container">$\#P\subseteq {PPAD}$</span> holds?</p>
</li>
</ol>
</blockquote>

CC BY-SA 3.0
2017-07-30T02:23:36.973Z
Would you mind adding a reference for your opening claim?
Daniel Apon
CC BY-SA 3.0
2017-07-30T02:42:28.993Z
@DanielApon $PPAD\subseteq NP$ is known.
Turbo
CC BY-SA 3.0
2017-07-30T04:55:29.553Z
@DanielApon I thought it follows from Toda's theorem.
Turbo
CC BY-SA 3.0
2017-07-30T18:13:32.300Z
PPAD is a class of search problems, not decision problems. Thus "NP = PPAD" is a meaningless string of symbols.
Emil Jeřábek
CC BY-SA 3.0
2017-07-30T20:02:30.670Z
@EmilJerabek page 2 just befor section 1.1 'where PPAD is a
subclass of NP that contains several important problems
that are suspected to be hard, including Nash' and section 2.2 'The reason
is that PPAD lies “between P and NP”'.
Turbo
CC BY-SA 3.0
2017-07-30T20:07:33.290Z
@EmilJerabek refer page 38 here https://books.google.com/books?id=YCu2alSw0w8C&pg=PA38&lpg=PA38&dq=PPAD+NP&source=bl&ots=aNxHxSmpx6&sig=Jwlqr83fL3NcMcV2TIIsugNxXdk&hl=en&sa=X&ved=0ahUKEwj2qI_15bHVAhWHq1QKHZXSCQ0Q6AEIRDAE#v=onepage&q=PPAD%20NP&f=false.
Turbo
CC BY-SA 3.0
2017-07-31T08:24:05.787Z
Well, I don’t know why they write it in this sloppy way, but it is still nonsense. See Papadimitriou’s paper to learn what PPAD actually is. Or just consult Wikipedia. PPAD is a subclass of TFNP.
Emil Jeřábek
CC BY-SA 3.0
2017-07-31T08:27:05.897Z
Also, $FP^{PPAD}$ is just PPAD (or its subset, if FP is taken to mean that the functions are single-valued), and I have no idea what makes you write $P^{FP^X}$ instead of just $P^X$.
Emil Jeřábek
CC BY-SA 3.0
2017-07-31T09:10:48.423Z
Correction: TFNP problems in $FP^{PPAD}$ are in PPAD. In a more general context, $FP^{PPAD}$ consists of search problems that are *projections* of PPAD problems (but then again, in this context it is better to redefine PPAD to be closed under projections).
Emil Jeřábek
CC BY-SA 3.0
2017-07-31T11:24:28.840Z
@EmilJeřábek taken your suggestion comment.
Turbo
CC BY-SA 3.0
2017-07-31T19:14:08.040Z
@777 this is better now =)
Daniel Apon
<cc.complexity-theory><complexity-classes><counting-complexity><polynomial-hierarchy><ppad>
What does $\#P\subseteq FP^{PPAD}$ imply?
Turbo
# What does $\#P\subseteq FP^{PPAD}$ imply?

(Asked by: username_0 on 2017-07-29)

We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment).

> 1. Can $\#P\subseteq {PPAD}$ give a stronger collapse such as $\oplus P=UP=NP=coNP=PP$ or $NP=coNP=P^{PPAD}$?
> 2. What other consequences follow in $\#P\subseteq {PPAD}$ holds?

**Tags:** cc.complexity-theory, complexity-classes, counting-complexity, polynomial-hierarchy, ppad

> **Comments:**
> **username_1**: Would you mind adding a reference for your opening claim?  
> **username_0**: @DanielApon $PPAD\subseteq NP$ is known.  
> **username_0**: @DanielApon I thought it follows from Toda's theorem.  
> **username_2**: PPAD is a class of search problems, not decision problems. Thus "NP = PPAD" is a meaningless string of symbols.  
> **username_0**: @EmilJerabek page 2 just befor section 1.1 'where PPAD is a subclass of NP that contains several important problems that are suspected to be hard, including Nash' and section 2.2 'The reason is that PPAD lies “between P and NP”'.  
> **username_0**: @EmilJerabek refer page 38 here https://books.google.com/books?id=YCu2alSw0w8C&pg=PA38&lpg=PA38&dq=PPAD+NP&source=bl&ots=aNxHxSmpx6&sig=Jwlqr83fL3NcMcV2TIIsugNxXdk&hl=en&sa=X&ved=0ahUKEwj2qI_15bHVAhWHq1QKHZXSCQ0Q6AEIRDAE#v=onepage&q=PPAD%20NP&f=false.  
> **username_2**: Well, I don’t know why they write it in this sloppy way, but it is still nonsense. See Papadimitriou’s paper to learn what PPAD actually is. Or just consult Wikipedia. PPAD is a subclass of TFNP.  
> **username_2**: Also, $FP^{PPAD}$ is just PPAD (or its subset, if FP is taken to mean that the functions are single-valued), and I have no idea what makes you write $P^{FP^X}$ instead of just $P^X$.  
> **username_2**: Correction: TFNP problems in $FP^{PPAD}$ are in PPAD. In a more general context, $FP^{PPAD}$ consists of search problems that are *projections* of PPAD problems (but then again, in this context it is better to redefine PPAD to be closed under projections).  
> **username_0**: @EmilJeřábek taken your suggestion comment.  
> **username_1**: @777 this is better now =)  

---

## 1 answers

### Answer by username_2 on 2017-07-31. Score: 3 | Accepted answer

First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq PPAD}$. Thus, if we assume
$$\mathrm{\#P\subseteq PPAD},$$
then
$$\mathrm{\#P^{PPAD}\subseteq PPAD},$$
which by induction implies
$$\mathrm{FCH=PPAD}.$$
Passing to decision problems, since $\mathrm{P^{PPAD}\subseteq P^{TFNP}\subseteq NP\cap coNP}$, this shows
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP}.$$
(Note that using the closure of $\mathrm{PPAD}$ under Turing reductions, $\mathrm{P^{PPAD}}$ consists of predicates whose characteristic functions can be computed as projections of $\mathrm{PPAD}$ problems.)

As for $\oplus\mathrm P$, I believe $\mathrm{PPA\supseteq PPAD}$ can be solved by binary search on the predicate “the sum of degrees of vertices whose labels start with a given string is odd”, which means
$$\mathrm{PPAD\subseteq FP^{\oplus P}},$$
thus (using $\mathrm{P^{\oplus P}=\oplus P}$)
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP=\oplus P}.$$
A similar argument applies with $\mathrm{Mod}\_p\mathrm P$ in place of $\oplus\mathrm P$ for any prime $p$.

I don’t know about UP.

> **Comments:**
> **username_0**: is it believed $Mod_pP\subseteq P/poly$ possible at $p\neq 2$?  
> **username_2**: It’s possible in the sense that we don’t know how to disprove it at the moment. However, it is quite unlikely, just like for $\oplus P$. To begin with, it would imply $\mathrm{PH\subseteq P/poly}$ by Toda’s theorem.  
> **username_1**: ( ͡° ͜ʖ ͡°) .....  
> **username_0**: @EmilJeřábek Does $$PP ⊆ coNP^{TFNP}⟹CH=PH=\Sigma_2∩\Pi_2=PP=\oplus P=coNP^{TFNP}∩NP^{TFNP}$$ hold? Essentially asking instead of $PPAD$ we assume $TFNP$ Oracle and/or instead of $P^{TFNP}$ we assume $(\Pi_i^P)^{TFNP}$ or $(\Sigma_i^P)^{TFNP}$ in polynomial hierarchy such as $(\Pi_2^P)^{TFNP}=(coNP)^{TFNP}$ can we expect similar collapse as in your answer to query?  
> **username_2**: The inclusion of PP in any subclass $C$ of ModPH collapses CH to $P^C$. However, you won’t get $PP=\oplus P$ that way, this relied on the connection of PPAD to parity.  
> **username_0**: @EmilJeřábek $\Sigma_i^P=\Pi_i^P=PH=PP=CH\implies\#\Sigma_{i-1}^P=\#\Sigma_{i}^P$ plausible? Would this give $U\Sigma_i^P=\Sigma_i^P=\Pi_i^P$ (theorem $61$ in Aspects of Complexity: Minicourses in Algorithmics, Complexity and Computational Algebra, Mathematics Workshop, Kaikoura, January 7-15, $2000$) (De Gruyter Series in Logic and Its Applications, 4) edited Rod G. Downey, Denis Roman Hirschfeldt). Here by $U\Sigma_i^P$ I mean the appropriate class in UAP (I think there should be such a class (where every alternation has unique accepting path) but not sure).  
> **username_0**: @EmilJeřábek If $PP$ is in $Mod_kP$ at a $k>2$ (say $k=15$) and odd would it follow $PP$ is in $\oplus P$?  
> **username_2**: I have frankly no idea what you are talking about. What is $\mathrm{FL^{SpanL}}$, where does your "we know" come from, and why on earth should it imply anything about FCH or PPAD?  
> **username_0**: @EmilJeřábek Sorry for not being clear. I was talking in the context of the question above and your answer. I think $\#P\subseteq FL^{SpanL}$ comes from https://www.sciencedirect.com/science/article/pii/030439759390252O (theorem 4.8). Then in the context of this question we seem to get $FCH=PPAD=FL^{SpanL}$ correct? Does it also give $\#P=SpanL$?  
> **username_2**: I see. Yes, the assumption also implies $\mathrm{FCH=FL^{SpanL}}$. I see no reason it should collapse anything down to SpanL.  
> **username_0**: @EmilJeřábek This was my thought. Please correct me if I am wrong. The way theorem $4.8$ works in that paper (I think) is first show given a Boolean function f in form of $3CNF$, the number of non-satisfying assignments is in $SpanL$. We subtract $2^n$ and this quantity in $Logspace$. ....  
> **username_0**: ...Now I am wondering if $CH=NP=coNP$ as in the answer to the posted question above holds, then given a $3CNF$ $f_1$ can we construct (in Logspace) another $3CNF$ $f_2$ such that the number of satisfying assignments in $f_1$ is the number of non-satisfying assignments in $f_2$? If we can do that then we don't have to subtract and directly get number of satisfying assignments by output of the $SpanL$ machine placing $\#P$ in $SpanL$.  
> **username_2**: NP = coNP implies there is a Logspace transformation of a 3CNF $f_1$ to a 3CNF $f_2$ such that $f_2$ is satisfiable iff $f_1$ is unsatisfiable. However, this is far from changing the number of satisfying assignments the way you want. In fact, what you write is impossible even disregarding the Logspace requirement because the numbers of satisfying assignments of 3CNF obey  strict constraints that are not symmetric: to begin with, the number of satisfying assignments of a 3CNF in $n$ variables is either $2^n$ or at most $7\cdot2^{n-3}$. Thus, if $f_1$ has a nonzero but small number of ...  
> **username_2**: ... satisfying assignments, then no such $f_2$ exists.  
> **username_0**: @EmilJeřábek I see OK. One last attempt. If $CH=NP$ or $CH=UP$ then to show $\#P=SpanL$ we only need to show $FNP=SpanL$ or $FUP=SpanL$ respectively right? Are these possible if $CH=NP$ or $CH=UP$ respectively?  
> **username_2**: I see no reason this should hold.  
> **username_0**: @EmilJeřábek I found one more thing. $UP=NP\iff SpanP=\#P$ holds. So in fact $\#L\subseteq SpanL\subseteq FL^{coUP}=FL^{UP}=\#P=SpanP=CH\subseteq FL^{SpanL}\subseteq FL^{UP}=FL^{coUP}$ holds according to your answer (I think). I do not know what this implies if say we assume $FUL=FNL=FPL=F\oplus L=\#L$ as well ($UL=NL$ is believed to be true). From the proof of the paper it seems $FL^{UP}\subseteq FL^{SpanL}$ holds. So I think  $\#L\subseteq SpanL\subseteq FL^{coUP}=FL^{UP}=\#P=SpanP=CH\subseteq FL^{SpanL}=FL^{UP}=FL^{coUP}$ might be true.  

---

