# Is there an oracle such that SAT is not infinitely often in sub-exponential time?

Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all instances of length $n$. (That is, this is the class of languages which can be "solved infinitely often, in subexponential time".)

Is there an oracle $A$ such that $NP^A \not\subset io$-$SUBEXP^A$? If we equip SAT with the oracle $A$ in the usual way, can we say that $SAT^A$ is not in this class?

(I'm asking separate questions here, because we have to be careful with infinitely-often time classes: just because you have a reduction from problem $B$ to problem $C$ and $C$ is solvable infinitely often, you may not actually get that $B$ is solvable infinitely often without further assumptions on the reduction: what if your reduction from $B$ "misses" the input lengths that you can solve $C$ on?)

• seems like an extension or variation on the Baker Gill Solovay 1975 idea? can it be contrasted somehow? – vzn Feb 24 '15 at 19:11

You can just take the oracle A s.t. NP$^A$=EXP$^A$ since EXP is not in i.o.-subexp. For SAT$^A$ it depends on the encoding, for example if the only valid SAT instances have even length then it is easy to solve SAT on odd-length strings. But if you use a language like $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$ then you should be fine.

• Do you have any references to the concept of io complexity classes and separations in the literature. In particular, I'm not quite sure why $EXP \nsubseteq io$-$SUBEXP$. In addition, do we have (1) $TIME(f(n)) \nsubseteq io$-$TIME(\frac{f(n)}{\log(f(n))})$ for appropriate functions f(n), and (2) $NP \subseteq io$-$P$ implies $P = NP$ (or at least $NP \subseteq P/ poly$)? – Michael Wehar Feb 26 '15 at 0:50
• I guess my main confusion is why can't every $EXP$-$Complete$ problem have an $io$-$SUBEXP$ algorithm that only solves the problem for a set of input lengths $X$ where $X$ is an $EXP$-$Complete$ set itself. – Michael Wehar Feb 26 '15 at 1:01
• In other words, the $io$-$SUBEXP$ algorithm doesn't help us because we would have to decide $X$ in order to know how to use the $io$-$SUBEXP$ algorithm. But, I wouldn't be surprised if existing work from you or others resolves my inquiry. – Michael Wehar Feb 26 '15 at 1:07
• @RyanWilliams Hi Ryan, any thoughts? Thanks for your time. :) – Michael Wehar Feb 27 '15 at 6:49
• @RyanWilliams Thanks for the comment! It helped and I think I got it worked out. Now, it seems that the argument didn't depend at all on EXP and this could be generalized to prove something like (1). But, the key point was "the opposite value on at least one input of that length". In other words, the argument in my head depends on io being defined as agreeing on infinitely many input lengths (not simply just infinitely many inputs). I still don't have much of an idea on something like (2). Thanks again and have a nice day/night. :) – Michael Wehar Feb 27 '15 at 10:08

You don't have to go to the lengths Lance was suggesting. For example, relative to a random oracle, using the oracle as a one-way function (say, evaluated on consecutive bit postions) is exponentially hard to invert on all but finitely many lengths.

This problem directly reduces to SAT on the same length input, so it does follow that SAT^A is not in infinitely often sub-exp.

• I should say the number of inputs to the circuit is the same, not the total instance size. However, if you are allowed to pad circuit sizes by adding redundant clauses,you should be able to make any fixed input size code a related one-way function. – Russell Impagliazzo Feb 26 '15 at 0:10