Theoretical Computer Science
cc.complexity-theory sat oracles
Updated Thu, 23 Jun 2022 08:26:35 GMT

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?)

Solution

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.

Comments (5)

  • +1 – 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$)? — Feb 26, 2015 at 00:50  
  • +0 – 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. — Feb 26, 2015 at 01:01  
  • +0 – 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. — Feb 26, 2015 at 01:07  
  • +0 – @RyanWilliams Hi Ryan, any thoughts? Thanks for your time. :) — Feb 27, 2015 at 06:49  
  • +1 – @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. :) — Feb 27, 2015 at 10:08  

References