<p>I found one related consequence.</p>

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

<p>On input $x$ of length $n$, consider the $n^{th}$ Turing machine $M$.  For every possible advice string of length $t$ <em>and</em> 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)})$.</p>

<p>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 <em>surviving</em> 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).</p>

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

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

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

CC BY-SA 3.0
2014-04-21T19:19:07.110Z
2014-04-21T19:19:07.110Z
GMB
<p>If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e.</p>

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

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

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

CC BY-SA 3.0
2014-04-17T22:39:45.763Z
Apologies if this question isn't appropriate for this site - I would be happy to improve the question however I can.
GMB
CC BY-SA 3.0
2014-04-18T05:23:09.163Z
I think this is an interesting question. An easy consequence similar to the separation of P from NP is that NP is not in DTime(o(t)/lg n).
Kaveh
CC BY-SA 3.0
2014-04-18T05:24:49.053Z
ps: I removed the second part because I think it is distracting and doesn't add much to the question.
Kaveh
CC BY-SA 3.0
2014-04-18T20:32:06.607Z
Thanks, Kaveh - I really appreciate the edit! (and from the vote swing, it seems everyone else does too)
GMB
<cc.complexity-theory><time-complexity><nondeterminism>
Consequences of nondeterminism speeding up deterministic computation
GMB
# Consequences of nondeterminism speeding up deterministic computation

(Asked by: username_0 on 2014-04-17)

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?

**Tags:** cc.complexity-theory, time-complexity, nondeterminism
> **Comments:**
> **username_0**: Apologies if this question isn't appropriate for this site - I would be happy to improve the question however I can.  
> **username_1**: I think this is an interesting question. An easy consequence similar to the separation of P from NP is that NP is not in DTime(o(t)/lg n).  
> **username_1**: ps: I removed the second part because I think it is distracting and doesn't add much to the question.  
> **username_0**: Thanks, Kaveh - I really appreciate the edit! (and from the vote swing, it seems everyone else does too)  

---

## 1 answers

### Answer by username_0 on 2014-04-21. Score: 2

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.


---

