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?

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

I don’t know about UP.

  • 1
    $\begingroup$ interesting that this gives $\oplus P=PP$. $\endgroup$ – 1.. Jul 31 '17 at 18:42
  • 1
    $\begingroup$ is it believed $Mod_pP\subseteq P/poly$ possible at $p\neq 2$? $\endgroup$ – 1.. Aug 1 '17 at 10:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Aug 1 '17 at 13:28
  • $\begingroup$ ( ͡° ͜ʖ ͡°) ..... $\endgroup$ – Daniel Apon Aug 4 '17 at 0:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Nov 29 '17 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.