15
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ 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. $\endgroup$
    – Greg Kuperberg
    Commented May 17, 2015 at 2:55
  • $\begingroup$ 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. $\endgroup$
    – Igor Pak
    Commented May 17, 2015 at 4:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – Greg Kuperberg
    Commented May 17, 2015 at 4:14
  • 2
    $\begingroup$ Ah, right. Interesting. Found it: Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane (2004). $\endgroup$
    – Igor Pak
    Commented May 17, 2015 at 7:34
  • 3
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented May 17, 2015 at 17:47

1 Answer 1

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 17, 2015 at 21:02
  • 1
    $\begingroup$ @Emil, the "verifier" inside parenthesis seems to clarify what Josh meant. $\endgroup$
    – Kaveh
    Commented May 18, 2015 at 0:21
  • $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented May 18, 2015 at 4:58
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 18, 2015 at 10:09
  • 1
    $\begingroup$ @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). $\endgroup$
    – Joshua Grochow
    Commented May 19, 2015 at 5:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.