# What does $\#P\subseteq FP^{PPAD}$ imply?

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?

• Would you mind adding a reference for your opening claim? – Daniel Apon Jul 30 '17 at 2:23
• @DanielApon $PPAD\subseteq NP$ is known. – Turbo Jul 30 '17 at 2:42
• @DanielApon I thought it follows from Toda's theorem. – Turbo Jul 30 '17 at 4:55
• PPAD is a class of search problems, not decision problems. Thus "NP = PPAD" is a meaningless string of symbols. – Emil Jeřábek Jul 30 '17 at 18:13
• @EmilJeřábek taken your suggestion comment. – Turbo Jul 31 '17 at 11:24

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$.
• interesting that this gives $\oplus P=PP$. – Turbo Jul 31 '17 at 18:42
• is it believed $Mod_pP\subseteq P/poly$ possible at $p\neq 2$? – Turbo Aug 1 '17 at 10:54
• 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 Aug 1 '17 at 13:28
• 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 Nov 29 '17 at 9:50