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?

  • $\begingroup$ Apologies if this question isn't appropriate for this site - I would be happy to improve the question however I can. $\endgroup$ – GMB Apr 17 '14 at 22:39
  • $\begingroup$ 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). $\endgroup$ – Kaveh Apr 18 '14 at 5:23
  • $\begingroup$ ps: I removed the second part because I think it is distracting and doesn't add much to the question. $\endgroup$ – Kaveh Apr 18 '14 at 5:24
  • $\begingroup$ Thanks, Kaveh - I really appreciate the edit! (and from the vote swing, it seems everyone else does too) $\endgroup$ – GMB Apr 18 '14 at 20:32

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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