0
$\begingroup$

Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).

I want to decide if the number of accepting paths $N_{accept}$ is $0$ or $>0$.

I can ask a $\oplus P$ oracle to decide if $2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ as $MOD_{2^m}P=MOD_2P$ by https://complexityzoo.net/Complexity_Zoo:M#modkp.

There are three different scenarios

  1. $2^t|N_{accept}$ and $2^{t+1}|N_{accept}$ in which case $N_{accept}=0$.

  2. $2^t|N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $N_{accept}=2^t$.

  3. $2^t\nmid N_{accept}$ and $2^{t+1}\nmid N_{accept}$ in which case $1\leq N_{accept}\leq2^t-1$.

So $N_{accept}=0\iff\oplus P$ oracle accepts twice.

Why would the above not place $coNP$ in $\oplus P$ or at least $NP^{\oplus P}$?

$\endgroup$
0
$\begingroup$

The result that $\mathrm{MOD}_{2^m}\mathrm P=\mathrm{MOD}_2\mathrm P$ only applies when $m$ is constant. Thus, your strategy only works if $t$ is constant, which is a trivial case. You would need it to apply to $t\approx n^c$. (Actually, the argument works for $m=O(\log n)$, but this is still not enough.)

Specifically, the reduction of $\mathrm{MOD}_{2^m}\mathrm P$ to $\mathrm{MOD}_2\mathrm P$ relies on the simple number-theoretic fact that $$2^m\mid s\iff2\mid s\land2\mid\binom s2\land2\mid\binom s{2^2}\land\dots\land2\mid\binom s{2^{m-1}}.$$ If $s$ counts the number of objects satisfying some property, then $\binom s{2^r}$ counts the number of $2^r$-element sets of objects with that property.

That is, given a language $L\in\mathrm{MOD}_{2^m}\mathrm P$ of the form $$w\in L\iff2^m\mid\#\{x<2^{n^c}:R(w,x)\},$$ where $n$ denotes $|w|$ and $R\in\mathrm P$, we can express $L$ as $$w\in L\iff\forall r<m\ 2\mid\#\{(x_0,\dots,x_{2^r-1})\in[0,2^{n^c})^{2^r}:R_r(w,x_0,\dots,x_{2^r-1})\},$$ where $$R_r(w,x_0,\dots,x_{2^r-1})\iff x_0<\dots<x_{2^r-1}\land\forall i<2^r\:R(w,x_i).$$ (These $m$ instances of $\oplus\mathrm P$ can be then combined to a single $\oplus\mathrm P$ predicate as $\oplus\mathrm P$ is closed under poly-time Turing reductions; in fact, even $\mathrm{\oplus P^{\oplus P}=\oplus P}$.)

As long as $m=O(\log n)$, the sequences $(x_0,\dots,x_{2^r-1})$ can be represented with $n^{O(1)}$ bits, and the predicates $R_r$ are computable polynomial time, but neither is true for larger $m$.

$\endgroup$
6
  • $\begingroup$ Why it breaks for $m=\omega(\log n)$? $\endgroup$ – User2021 Mar 20 at 9:39
  • $\begingroup$ The reduction will no longer be polynomial. $\endgroup$ – Emil Jeřábek Mar 20 at 9:40
  • $\begingroup$ If you can illustrate it would be helpful (theorem $7.3$ was unclear in sciencedirect.com/science/article/pii/030439759290084S). Is it related to $TC^0\not\subseteq AC^0[\oplus P]$? $\endgroup$ – User2021 Mar 20 at 9:41
  • $\begingroup$ Since you are looking at this paper, you can find the reduction of MOD_{p^m} to MOD_p in Theorem 7.2, which explains it quite well. I can’t make much sense of your second sentence. If your argument applied to $m$ polynomial in $n$, it would not only show $\mathrm{coNP}\subseteq\oplus\mathrm P$ as you wrote, but it would actually show $\mathrm{PP}\subseteq\oplus\mathrm P$, if this is what you are asking. $\endgroup$ – Emil Jeřábek Mar 20 at 9:53
  • $\begingroup$ Yes I believe we can get $PP$ in $\oplus P$ if the logic worked. So is it related to $TC^0\not\subseteq AC^0[\oplus P]$? $\endgroup$ – User2021 Mar 20 at 10:01

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.