vs

Em nosso trabalho recente, resolvemos um problema computacional que surgiu no contexto combinatório, pressupondo que , onde$\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ é aversão E X P de$\mathsf{\oplus{}EXP}$$\mathsf{EXP}$ . O único artigo sobre$\mathsf{\oplus{}P}$ que encontramos foi o artigo de Beigel-Buhrman-Fortnow, de1998,citado noComplexity Zoo. Entendemos que podemos ter versões paritárias deproblemascompletosde N E X P (consulteesta pergunta), mas talvez muitos deles não sejam completos em$\mathsf{\oplus{}EXP}$$\mathsf{NEXP}$ . $\mathsf{\oplus{}EXP}$

PERGUNTA: Existem razões de complexidade para acreditar que ? Existem problemas combinatórios naturais que são completos em$\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ ? Existem algumas referências que podem estar faltando? $\mathsf{\oplus{}EXP}$

Em termos de razões de complexidade (em vez de problemas completos): O Hartmanis-Immerman-Sewelson Teorema também deve funcionar, neste contexto, a saber: sse existe um conjunto polinomialmente escasso em ⊕ P ∖ P . Dado o quão distantes pensamos que P e ⊕ P estão - por exemplo, Toda mostrou que P H ⊆ B P P ⊕ P - seria bastante surpreendente se não houvesse conjuntos esparsos em suas diferenças.$\mathsf{EXP} \neq \oplus \mathsf{EXP}$$\oplus \mathsf{P} \backslash \mathsf{P}$$\mathsf{P}$$\oplus \mathsf{P}$$\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$

Mais diretamente, se não houvesse conjuntos esparsos em suas diferenças, diria que para todo verificador , se o número de cadeias de comprimento n com um número ímpar de testemunhas for limitado por n O ( 1 $\mathsf{NP}$$n$$n^{O(1)}$ , então o problema [ de dizer se existe um número ímpar de testemunhas] deve estar em . Isso parece um fato bastante impressionante e improvável.$\mathsf{P}$