30
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ seems like an extension or variation on the Baker Gill Solovay 1975 idea? can it be contrasted somehow? $\endgroup$
    – vzn
    Commented Feb 24, 2015 at 19:11

2 Answers 2

Reset to default
26
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ 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$)? $\endgroup$
    – Michael Wehar
    Commented Feb 26, 2015 at 0:50
  • $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Commented Feb 26, 2015 at 1:01
  • $\begingroup$ 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. $\endgroup$
    – Michael Wehar
    Commented Feb 26, 2015 at 1:07
  • $\begingroup$ @RyanWilliams Hi Ryan, any thoughts? Thanks for your time. :) $\endgroup$
    – Michael Wehar
    Commented Feb 27, 2015 at 6:49
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – Michael Wehar
    Commented Feb 27, 2015 at 10:08
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Russell Impagliazzo
    Commented Feb 26, 2015 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.