14
$\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?

$\endgroup$
  • 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 May 17 '15 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 May 17 '15 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 May 17 '15 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 May 17 '15 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 May 17 '15 at 17:47
13
$\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.

$\endgroup$
  • $\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 May 17 '15 at 21:02
  • 1
    $\begingroup$ @Emil, the "verifier" inside parenthesis seems to clarify what Josh meant. $\endgroup$ – Kaveh May 18 '15 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 May 18 '15 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 May 18 '15 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 May 19 '15 at 5:40

Your Answer

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

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