<p>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.  </p>

<p>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.</p>

CC BY-SA 3.0
2015-02-26T00:10:48.223Z
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
CC BY-SA 3.0
2015-02-26T00:07:35.673Z
2015-02-26T00:07:35.673Z
Russell Impagliazzo
<p>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.</p>

CC BY-SA 3.0
2015-02-26T00:50:40.527Z
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
CC BY-SA 3.0
2015-02-26T01:01:16.587Z
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
CC BY-SA 3.0
2015-02-26T01:07:35.480Z
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
CC BY-SA 3.0
2015-02-27T06:49:23.717Z
@RyanWilliams Hi Ryan, any thoughts?  Thanks for your time.  :)
Michael Wehar
CC BY-SA 3.0
2015-02-27T07:11:36.517Z
EXP isn't in io SUBEXP, because in EXP we can diagonalize against (for example) the first n subexp time TMs, on the inputs of length n. Eventually, any particular subexp TM will appear among the first n, and on almost every input length our EXP machine can output the opposite value on at least one input of that length. I don't know of a reference that studies io things in detail but they appear in many papers.
Ryan Williams
CC BY-SA 3.0
2015-02-27T10:08:01.580Z
@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
CC BY-SA 3.0
2015-02-27T23:46:13.800Z
When I said defining io-SUBEXP as agreeing on infinitely many inputs, I guess I meant like a promise problem where we want a subexponential time algorithm that always correctly outputs either yes, no, or I don't know and outputs yes or no infinitely often.
Michael Wehar
CC BY-SA 3.0
2015-02-24T11:49:02.020Z
2015-02-24T11:49:02.020Z
Lance Fortnow
<p>Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon &gt; 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".)</p>

<p>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? </p>

<p>(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?)</p>

CC BY-SA 3.0
2015-02-24T19:11:00.890Z
seems like an extension or variation on the Baker Gill Solovay 1975 idea? can it be contrasted somehow?
vzn
<cc.complexity-theory><sat><oracles>
Is there an oracle such that SAT is not infinitely often in sub-exponential time?
Ryan Williams
# Is there an oracle such that SAT is not infinitely often in sub-exponential time?

(Asked by: username_0 on 2015-02-23)

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

**Tags:** cc.complexity-theory, sat, oracles
> **Comments:**
> **username_1**: seems like an extension or variation on the Baker Gill Solovay 1975 idea? can it be contrasted somehow?  

---

## 2 answers

### Answer by username_3 on 2015-02-24. Score: 26 | Accepted answer

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:**
> **username_4**: 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$)?  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_4**: @RyanWilliams Hi Ryan, any thoughts?  Thanks for your time.  :)  
> **username_0**: EXP isn't in io SUBEXP, because in EXP we can diagonalize against (for example) the first n subexp time TMs, on the inputs of length n. Eventually, any particular subexp TM will appear among the first n, and on almost every input length our EXP machine can output the opposite value on at least one input of that length. I don't know of a reference that studies io things in detail but they appear in many papers.  
> **username_4**: @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.  :)  
> **username_4**: When I said defining io-SUBEXP as agreeing on infinitely many inputs, I guess I meant like a promise problem where we want a subexponential time algorithm that always correctly outputs either yes, no, or I don't know and outputs yes or no infinitely often.  

---

### Answer by username_2 on 2015-02-26. Score: 16

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.

> **Comments:**
> **username_2**: 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.  

---

