vs

En nuestro trabajo reciente, resolvemos un problema computacional que surgió en un contexto combinatorio, suponiendo que , donde es el -versión de . El único artículo sobre que encontramos fue el artículo de Beigel-Buhrman-Fortnow 1998 que se cita en Complexity Zoo . Entendemos que podemos tomar versiones de paridad de problemas completos (vea esta pregunta ), pero tal vez muchos de ellos no estén completos en ⊕$\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$$\mathsf{\oplus{}EXP}$$\mathsf{EXP}$$\mathsf{\oplus{}P}$$\mathsf{\oplus{}EXP}$$\mathsf{NEXP}$$\mathsf{\oplus{}EXP}$ .

PREGUNTA: ¿Existen razones complejas para creer que ? ¿Hay problemas combinatorios naturales que están completos en? ¿Hay algunas referencias que podríamos estar perdiendo? $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$$\mathsf{\oplus{}EXP}$

En cuanto a los motivos de complejidad (en lugar de problemas completas): El Hartmanis-Immerman-Sewelson teorema también debe trabajar en este contexto, a saber: si y sólo si existe un conjunto polinómicamente escasa en ⊕ P ∖ P . Dado cuán separados creemos que P y ⊕ P están, por ejemplo, Toda demostró que P H ⊆ B P P ⊕ P - sería bastante sorprendente si no hubiera conjuntos dispersos en su diferencia.$\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}}$

Más directamente, si no hubiera conjuntos dispersos en su diferencia, diría que por cada verificador , si el número de cadenas de longitud n con un número impar de testigos está limitado por n O ( 1 ) , entonces el problema [ de decir si hay un número impar de testigos] debe estar en P . Esto parece un hecho bastante sorprendente e improbable.$\mathsf{NP}$$n$$n^{O(1)}$$\mathsf{P}$