Consequences of nondeterminism speeding up deterministic computation

Question

If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e.

for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$,

then if follows from the deterministic time hierarchy theorem that $\mathsf{P} \subsetneq \mathsf{NP}$.

But are there any other interesting consequences nontrivial (i.e. not a consequence of $\mathsf{P} \subsetneq \mathsf{NP}$) if nondeterminism can speed up deterministic computations?

Answer 1

I found one related consequence.

Let's say $NEXP$ contains $DTIME(2^{O(t)})$, where $t = n^{\omega(1)}$. It turns out this is just enough time to diagonalize against $P/poly$. Specifically, build the following machine:

On input $x$ of length $n$, consider the $n^{th}$ Turing machine $M$. For every possible advice string of length $t$ and every possible bitstring $b$ of length $n$, run $M$ on $b$ with advice $a$, and reject after $t$ steps if you haven't accepted yet. Record your results in a table. This procedure runs in $DTIME(2^{O(t)})$.

On input $0^n$, if at least half the advice strings cause $M$ to reject, then instead we define it to be correct for our algorithm to accept (otherwise, it is correct for our algorithm to reject). Any advice strings that caused $M$ to get $0^n$ wrong (that is, at least half the advice strings) now get thrown out of the table. We then repeat the process on input $0^{n-1}1$: if at least half the surviving advice strings cause $M$ to reject, then our algorithm will accept (and reject otherwise). Continue like this for all inputs of length $n$ (although really, only $t$ of them are needed - after that many inputs, we have thrown out all possible advice strings).

Clearly this language can be decided in $DTIME(2^{O(t)})$, which we have assumed is in $NEXP$. On the other hand, it cannot be in $P/Poly$: the set of length $n$ inputs diagonalizes against the prospect of $M_n$ being used to decide the language.

So we get $NEXP \not \subset P/poly$, which would be interesting.

I'm going to leave the question open in case someone comes up with something else.