<p>$\text{Mod}_k\text{P}$ is the class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."</p>

<p>For constant $k$, one can find the number of accepting paths of an NP machine mod $k$ by querying a $\text{Mod}_k\text{P}$ oracle with $0$,$1$,$2$,$\ldots$,$k-1$ accepting paths added to the original NP machine. Are there more interesting functions one can compute with oracle access to a $\text{Mod}_k\text{P}$-complete problem?  For instance, does $\text{P}^{\text{Mod}_k\text{P}} =\text{P}^{\#\text{P}}$? It is clear that $\text{P}^{\text{Mod}_k\text{P}} \subseteq \text{P}^{\#\text{P}}$.</p>

<p>For $k=2$, we have that $\text{Mod}_k\text{P} = \oplus \text{P}$, and certain hard problems (like computing the permanent) become easy mod 2.  Therefore, we might expect the power of $\text{P}^{\text{Mod}_k\text{P}}$ to depend on $k$.  </p>

CC BY-SA 3.0
2016-07-12T18:29:27.730Z
Note that while *specific* functions can become easier modulo certain $k$ (e.g. permanent), the power of $\mathsf{Mod_k P}$ as a complexity class seems to me very unlikely to depend on anything more than the exponents in the prime factorization of $k$ (and not specifically which primes appear). For example, Toda's Theorem works for any $k$.
Joshua Grochow
CC BY-SA 3.0
2016-07-12T18:56:03.333Z
Yes. You could be right about that.  Actually, though, the power of  $\text{Mod}_k\mathsf{P}$ is determined solely by the prime factorization of $k$.  See, for instance, the conclusion of Hertrampf in http://www.sciencedirect.com/science/article/pii/030439759090081R
Daniel Grier
<cc.complexity-theory>
$\text{P}^{\text{Mod}_k\text{P}}$ vs $\text{P}^{\#\text{P}}$?
Daniel Grier
# $\text{P}^{\text{Mod}_k\text{P}}$ vs $\text{P}^{\#\text{P}}$?

(Asked by: username_0 on 2016-07-12)

$\text{Mod}\_k\text{P}$ is the class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."

For constant $k$, one can find the number of accepting paths of an NP machine mod $k$ by querying a $\text{Mod}\_k\text{P}$ oracle with $0$,$1$,$2$,$\ldots$,$k-1$ accepting paths added to the original NP machine. Are there more interesting functions one can compute with oracle access to a $\text{Mod}\_k\text{P}$-complete problem? For instance, does $\text{P}^{\text{Mod}\_k\text{P}} =\text{P}^{\#\text{P}}$? It is clear that $\text{P}^{\text{Mod}\_k\text{P}} \subseteq \text{P}^{\#\text{P}}$.

For $k=2$, we have that $\text{Mod}\_k\text{P} = \oplus \text{P}$, and certain hard problems (like computing the permanent) become easy mod 2. Therefore, we might expect the power of $\text{P}^{\text{Mod}\_k\text{P}}$ to depend on $k$.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Note that while *specific* functions can become easier modulo certain $k$ (e.g. permanent), the power of $\mathsf{Mod_k P}$ as a complexity class seems to me very unlikely to depend on anything more than the exponents in the prime factorization of $k$ (and not specifically which primes appear). For example, Toda's Theorem works for any $k$.  
> **username_0**: Yes. You could be right about that.  Actually, though, the power of  $\text{Mod}_k\mathsf{P}$ is determined solely by the prime factorization of $k$.  See, for instance, the conclusion of Hertrampf in http://www.sciencedirect.com/science/article/pii/030439759090081R  

---

## 0 answers

