I've been stuck on this question for hours, can't seem to figure this out.
$L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and there is some computation of $M$ on $x$ that accepts in $\le |y|$ steps $\}$
I need to show that $L \in NP$.
What I was thinking was to demonstrate that we can create another Turing machine $M'$ and simulate $M$ on $x$, showing that the simulation itself only takes polynomial time over the input size $n$, however I am not sure of this or how it would work. Any hints appreciated.
Best Answer
Showing a language is in $NP$ is easy without a reduction. The reduction is important when looking at NP-Completeness or NP-Hardness.
So to show $L \in NP$, we need to show that there is a decision problem and that an answer of "yes" can be verified in $O(p(|s|))$ time, where $|s|$ is the length of the input string. The decision problem is pretty obvious.
So since $|y| < |<M, x, y>|$, it clearly takes at most $|y|$ steps to verify a yes. So we have $O(n)$ time verification, which is polynomial. Your idea of using a Turing Machine $M^{\prime}$ to simulate $M$ on $x$ is spot on.
So $L \in NP$.