vs

Dalam karya terbaru kami, kami menyelesaikan masalah komputasi yang muncul dalam konteks kombinatorial, dengan asumsi bahwa , di mana$\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ adalah versi E X P dari$\mathsf{\oplus{}EXP}$$\mathsf{EXP}$ . Satu-satunya kertas di$\mathsf{\oplus{}P}$ yang kami temukan adalahmakalahBeigel-Buhrman-Fortnow1998yang dikutip diComplexity Zoo. Kami memahami bahwa kita dapat mengambil versi paritas N E X P masalah -Lengkap (lihatpertanyaan ini), tapi mungkin banyak dari mereka sebenarnya tidak lengkap dalam$\mathsf{\oplus{}EXP}$$\mathsf{NEXP}$ . $\mathsf{\oplus{}EXP}$

PERTANYAAN: Apakah ada alasan kompleksitas untuk percaya bahwa ? Apakah ada masalah kombinatorial alami yang lengkap dalam$\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$ ? Apakah ada beberapa referensi yang mungkin kita lewatkan? $\mathsf{\oplus{}EXP}$

Dalam hal alasan kompleksitas (bukan masalah lengkap): The Hartmanis-Immerman-Sewelson Teorema juga harus bekerja dalam konteks ini, yaitu: IFF ada satu set polynomially jarang di ⊕ P ∖ P . Mengingat seberapa jauh kita berpikir P dan ⊕ P - misalnya Toda menunjukkan bahwa P H ⊆ B P P ⊕ $\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}}$ - itu akan cukup mengejutkan jika tidak ada set jarang dalam perbedaan mereka.

Lebih langsung, jika tidak ada set jarang dalam perbedaan mereka, itu akan mengatakan bahwa untuk setiap verifier, jika jumlah string dengan panjang n dengan jumlah ganjil saksi dibatasi oleh n O ( 1 ) , maka masalah [ menceritakan apakah ada ganjil saksi] harus dalam P . Ini sepertinya fakta yang cukup mengejutkan dan tidak mungkin.$\mathsf{NP}$$n$$n^{O(1)}$$\mathsf{P}$