Is there a language not in NP but for which exists a Non-deterministic TM which accepts/rejects strings based on belonging to the language?

780 Views Asked by At

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$.