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$
17
  • 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
  • 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
  • 1
    $\begingroup$ I see. Yes, the assumption also implies $\mathrm{FCH=FL^{SpanL}}$. I see no reason it should collapse anything down to SpanL. $\endgroup$
    – Emil Jeřábek
    May 19 at 17:26
  • 1
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    May 20 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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