# $coNP$ and $\oplus P$?

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}$$?

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 where $$R_r(w,x_0,\dots,x_{2^r-1})\iff x_0<\dots (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$$.

• Why it breaks for $m=\omega(\log n)$? – User2021 Mar 20 at 9:39
• The reduction will no longer be polynomial. – Emil Jeřábek Mar 20 at 9:40
• 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]$? – User2021 Mar 20 at 9:41
• 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. – Emil Jeřábek Mar 20 at 9:53
• 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]$? – User2021 Mar 20 at 10:01