0

Is there a language $L$ such that $L \notin NP$, and $\exists$ Non-deterministic Turing Machine $M$: $\forall l \in L$ : $M$ accepts $l$, $\forall l \notin L$ : $M$ rejects $L$?

A side-question. Are the following two statements equivalent?

$\exists$ Non-deterministic Turing Machine $M$: $\forall l \in L$ : $M$ accepts $l$, $\forall l \notin L$ : $M$ rejects $L$.

$\exists$ Deterministic Turing Machine $M$: $\forall l \in L$ : $M$ accepts $l$, $\forall l \notin L$ : $M$ rejects $L$.

CrabMan
  • 1,123
  • 7
  • 16
  • $L \in NP$ means that there is a Non-deterministic Turing Machine that accepts/rejects the language in polynomial time. – CrabMan Jul 15 '16 at 20:27
  • that's what I said :) so what you need is a very hard to recognize language, for example encode the integer $n$ with $\underbrace{a\dots a}_n$ and let $L = { \underbrace{a\dots a}_n \ | $ the $2^{2^{2^n}}$th prime is $\equiv 1 \bmod 4}$ – reuns Jul 15 '16 at 20:36

1 Answers1

2

Yes. By the time hierarchy theorem, there are problems that are technically decidable by a nondeterministic Turing machine, just not very efficiently. More precisely, there are problems in NEXPTIME which aren't in NP.

This means that there is a language $L\in \mathrm{NEXPTIME} - \mathrm{NP}$. For such a language, there's a nondeterministic Turing machine that reads its input, runs for an exponential number of steps, then halts with accept if the input is in $L$, or halts with reject if it isn't. Furthermore, $L$ isn't in NP, so no nondeterministic Turing machine runs for a polynomial number of steps before correctly deciding membership in $L$.

Yes, those two statements are equivalent. A deterministic Turing machine can simulate a non-deterministic TM, and vice-versa. They have identical power, and decide the same languages.

user326210
  • 17,287