# $\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{EXP}$-version of $\mathsf{\oplus{}P}$. The only paper on $\mathsf{\oplus{}EXP}$ that we found was the Beigel-Buhrman-Fortnow 1998 paper that is cited on Complexity Zoo. We understand that we can take parity versions of $\mathsf{NEXP}$-complete problems (see this question), but perhaps many of them are in fact not complete in $\mathsf{\oplus{}EXP}$.

QUESTION: Are there complexity reasons to believe that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$? Are there natural combinatorial problems that are complete in $\mathsf{\oplus{}EXP}$? Are there some references we might be missing?

• I think that parity versions of at least some NEXP-complete problems would be ⊕𝖤𝖷𝖯-complete for the same reason, e.g., SUCCINCT 3SAT. Parity classes are syntactic" just like existential non-determinism, so you have the same standard methods to make complete problems. – Greg Kuperberg May 17 '15 at 2:55
• Thanks, Greg. I understand. Not all problems will work though, e.g. the parity of the number of 3-colorings of SUCCINCT graphs is easy. – Igor Pak May 17 '15 at 4:09
• The issue in your example of the parity of the number of 3-colorings (which of course is divisible by 6) is orthogonal to the stated question of EXP-level complexity classes. The issue there is whether there is a parsimonious reduction, i.e., a reduction that preserves the number of witnesses. That is often known, but sometimes not. For instance, in the case of 3-colorings, there is a beautiful paper by Barbanchon (that I recently saw for my own reasons) that gives a parsimonious reduction from SAT, except for the factor of 6. – Greg Kuperberg May 17 '15 at 4:14
• Ah, right. Interesting. Found it: Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane (2004). – Igor Pak May 17 '15 at 7:34
• @GregKuperberg: Seems like an answer! Note that Valiant showed (people.seas.harvard.edu/~valiant/focs06.pdf) that even $\oplus 2SAT$ is $\oplus \mathsf{P}$-complete. – Joshua Grochow May 17 '15 at 17:47

In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely: $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ iff there is a polynomially sparse set in $\oplus \mathsf{P} \backslash \mathsf{P}$. Given how far apart we think $\mathsf{P}$ and $\oplus \mathsf{P}$ are - e.g. Toda showed that $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$ - it would be quite surprising if there were no sparse sets in their difference.
More directly, if there were no sparse sets in their difference, it would say that for every $\mathsf{NP}$ verifier, if the number of strings of length $n$ with an odd number of witnesses is bounded by $n^{O(1)}$, then the problem [of telling whether there is an odd number of witnesses] must be in $\mathsf{P}$. This seems like quite a striking and unlikely fact.