2
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Would you mind adding a reference for your opening claim? $\endgroup$
    – Daniel Apon
    Jul 30, 2017 at 2:23
  • $\begingroup$ @DanielApon $PPAD\subseteq NP$ is known. $\endgroup$
    – Turbo
    Jul 30, 2017 at 2:42
  • $\begingroup$ @DanielApon I thought it follows from Toda's theorem. $\endgroup$
    – Turbo
    Jul 30, 2017 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, 2017 at 18:13
  • 1
    $\begingroup$ @EmilJeřábek taken your suggestion comment. $\endgroup$
    – Turbo
    Jul 31, 2017 at 11:24

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ interesting that this gives $\oplus P=PP$. $\endgroup$
    – Turbo
    Jul 31, 2017 at 18:42
  • 1
    $\begingroup$ is it believed $Mod_pP\subseteq P/poly$ possible at $p\neq 2$? $\endgroup$
    – Turbo
    Aug 1, 2017 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, 2017 at 13:28
  • $\begingroup$ ( ͡° ͜ʖ ͡°) ..... $\endgroup$
    – Daniel Apon
    Aug 4, 2017 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, 2017 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.