Czy istnieje taka wyrocznia, że ​​SAT nie jest nieskończenie często w czasie sub wykładniczym?

Zdefiniuj $io$ - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).$SUBEXP$L ′ ∈ ∩ ε > $L$$L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$$n$$L$$L'$$n$

Czy istnieje wyrocznia $A$ taka, że $NP^A \not\subset io$ - $SUBEXP^A$ ? Jeśli wyposażymy SAT w wyrocznię $A$ w zwykły sposób, czy możemy powiedzieć, że $SAT^A$ nie ma w tej klasie?

(Zadaję tutaj osobne pytania, ponieważ musimy zachować ostrożność przy nieskończenie częstych zajęciach czasowych: tylko dlatego, że masz redukcję z problemu $B$ do problemu $C$ a $C$ można rozwiązać nieskończenie często, może nie być tak, że $B$ można rozwiązać nieskończenie często bez dalszych założeń dotyczących redukcji: co zrobić, jeśli redukcja z $B$ „pomija” długości wejściowe, na których można rozwiązać $C$ ?)

Możesz wziąć wyrocznię A st NP = EXP ponieważ EXP nie znajduje się w io-subexp. W przypadku SAT zależy to od kodowania, na przykład jeśli jedyne prawidłowe instancje SAT mają parzystą długość, wówczas łatwo jest rozwiązać SAT na ciągach nieparzystych. Ale jeśli używasz języka takiego jak to powinieneś być w porządku.A L = { ϕ 01 ∗ | ϕ ∈ S A T A$^A$$^A$$^A$$L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Nie musisz iść na całość, którą sugerował Lance. Na przykład, w stosunku do losowej wyroczni, użycie wyroczni jako funkcji jednokierunkowej (powiedzmy, ocenianej na kolejnych pozycjach bitów) jest wykładniczo trudne do odwrócenia na wszystkich, ale nieskończenie wielu długościach.

Ten problem bezpośrednio redukuje się do SAT na tej samej długości wejścia, więc wynika z tego, że SAT ^ A nie jest nieskończenie często sub-exp.