4
$\begingroup$

$\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$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Jul 12 '16 at 18:29
  • $\begingroup$ 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 sciencedirect.com/science/article/pii/030439759090081R $\endgroup$ – Daniel Grier Jul 12 '16 at 18:56
  • $\begingroup$ @DanielGrier : ​ $k$ is also determined "by the prime factorization of $k$", so the relevant part of that paper is that Mod$_k$P "is determined solely by" which primes divide $k$; i.e., the multiplicity of those primes doesn't matter. ​ ​ ​ ​ $\endgroup$ – user6973 Jul 12 '16 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.