vs

W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje parzystości problemy (zobacz to pytanie ), ale być może wiele z nich w rzeczywistości nie jest kompletnych w . $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$$\mathsf{\oplus{}EXP}$$\mathsf{EXP}$$\mathsf{\oplus{}P}$$\mathsf{\oplus{}EXP}$$\mathsf{NEXP}$$\mathsf{\oplus{}EXP}$

PYTANIE: Czy istnieją powody, by sądzić, że ? Czy w występują naturalne problemy kombinatoryczne ? Czy są jakieś referencje, których możemy brakować? $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$$\mathsf{\oplus{}EXP}$

Pod względem złożoności przyczyn (zamiast kompletnych problemy): Hartmanis-Immerman-Sewelson Twierdzenie powinny również działać w tym kontekście, a mianowicie: wtw istnieje wielomianowo rzadki zestaw w ⊕ P ∖ P . Biorąc pod uwagę, jak daleko od siebie myślimy P i ⊕ P - np. Toda wykazał, że P H ⊆ B P P ⊕ P - byłoby dość zaskakujące, gdyby nie było rzadkich zbiorów w ich różnicy.$\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ówiąc dokładniej, gdyby nie było rzadkich zestawów w ich różnicy, powiedziałoby to, że dla każdego weryfikatora , jeśli liczba ciągów długości n o nieparzystej liczbie świadków jest ograniczona przez n O ( 1 ) , to problem [ z informacją, czy jest nieparzysta liczba świadków] musi być P . To wydaje się dość uderzającym i mało prawdopodobnym faktem.$\mathsf{NP}$$n$$n^{O(1)}$$\mathsf{P}$