<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2015-05-17T21:02:18.400Z
I don't understand the last part. Any NP problem can be expressed in such a way that the number of witnesses is always even, and 0 is surely polynomially bounded, hence you are effectively saying that P = NP, and I don't see how that follows.
Emil Jeřábek
CC BY-SA 3.0
2015-05-18T00:21:19.643Z
@Emil, the "verifier" inside parenthesis seems to clarify what Josh meant.
Kaveh
CC BY-SA 3.0
2015-05-18T04:58:48.193Z
@EmilJeřábek: Indeed, Kaveh got it exactly. As you point out, the statement only really works if you talk about every NP verifier, rather than every NP problem. I've edited the answer so that this is no longer a parenthetical comment.
Joshua Grochow
CC BY-SA 3.0
2015-05-18T10:09:10.410Z
Sorry, but this didn't clarify anything. If the statement applies to all verifiers, it in particular applies to verifiers that always have an even number of witnesses.
Emil Jeřábek
CC BY-SA 3.0
2015-05-18T13:33:21.473Z
Hmm. Perhaps “the problem” refers to a different problem than what it looks like?
Emil Jeřábek
CC BY-SA 3.0
2015-05-19T05:40:05.867Z
@EmilJeřábek: Ah, yes, I see your confusion now (I think). Clarified. The result seems a little less striking to me, but not much (especially light of Toda's result).
Joshua Grochow
CC BY-SA 3.0
2015-05-17T17:44:38.427Z
2015-05-19T05:40:10.393Z
2015-05-19T05:40:10.393Z
Joshua Grochow
<p>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 <a href="http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf" rel="nofollow noreferrer">1998 paper</a> that is cited  on <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Symbols" rel="nofollow noreferrer">Complexity Zoo</a>. We understand that we can take parity versions of $\mathsf{NEXP}$-complete problems (see <a href="https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems">this question</a>), but perhaps many of them are in fact not complete in $\mathsf{\oplus{}EXP}$.  </p>

<p>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?   </p>

CC BY-SA 3.0
2015-05-17T02:55:58.130Z
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
CC BY-SA 3.0
2015-05-17T04:09:24.230Z
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
CC BY-SA 3.0
2015-05-17T04:14:07.027Z
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
CC BY-SA 3.0
2015-05-17T07:34:44.630Z
Ah, right.  Interesting.  Found it: Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane (2004).
Igor Pak
CC BY-SA 3.0
2015-05-17T17:47:06.417Z
@GregKuperberg: Seems like an answer! Note that Valiant showed (http://people.seas.harvard.edu/~valiant/focs06.pdf) that even $\oplus 2SAT$ is $\oplus \mathsf{P}$-complete.
Joshua Grochow
<cc.complexity-theory><complexity-classes><conditional-results><structural-complexity>
$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$
Igor Pak
# $\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

(Asked by: username_0 on 2015-05-16)

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](http://people.cs.uchicago.edu/~fortnow/papers/newiso.pdf) that is cited on [Complexity Zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Symbols). We understand that we can take parity versions of $\mathsf{NEXP}$-complete problems (see [this question](https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems)), 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?

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, structural-complexity

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: Ah, right.  Interesting.  Found it: Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane (2004).  
> **username_2**: @GregKuperberg: Seems like an answer! Note that Valiant showed (http://people.seas.harvard.edu/~valiant/focs06.pdf) that even $\oplus 2SAT$ is $\oplus \mathsf{P}$-complete.  

---

## 1 answers

### Answer by username_2 on 2015-05-17. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_3**: I don't understand the last part. Any NP problem can be expressed in such a way that the number of witnesses is always even, and 0 is surely polynomially bounded, hence you are effectively saying that P = NP, and I don't see how that follows.  
> **username_4**: @Emil, the "verifier" inside parenthesis seems to clarify what Josh meant.  
> **username_2**: @EmilJeřábek: Indeed, username_4 got it exactly. As you point out, the statement only really works if you talk about every NP verifier, rather than every NP problem. I've edited the answer so that this is no longer a parenthetical comment.  
> **username_3**: Sorry, but this didn't clarify anything. If the statement applies to all verifiers, it in particular applies to verifiers that always have an even number of witnesses.  
> **username_3**: Hmm. Perhaps “the problem” refers to a different problem than what it looks like?  
> **username_2**: @EmilJeřábek: Ah, yes, I see your confusion now (I think). Clarified. The result seems a little less striking to me, but not much (especially light of Toda's result).  

---

