Question about what it means to be in "NP"

Question

Suppose I am trying to prove language $L$ is in NP. Does it suffice to construct a nondeterministic Turing machine that accepts all strings in the language in polynomial time? Or must the machine also reject all strings not in the language in polynomial time?

Is it okay for the machine to loop forever on strings not in the language, as long as it accepts all strings that are in the language (in polynomial time)?

Thanks

Answer 1

If you had a nondeterministic TM that accepts just the strings in $L$ in polynomial time but takes more time, or even takes forever, on strings not in $L$, then you could design a modification of your machine that still accepts just the strings in $L$ but always halts in polynomial time. The idea of the modification is to build a "clock" into your machine. In more detail, the modified machine begins by counting how long its input string is, then it computes a suitable polynomial function of that length which is to serve as a time limit, and then it simulates the original machine while counting down from the time limit. If the countdown reaches $0$ before the computation is complete, the machine rejects and halts.

Answer 2

Suppose $L$ is the language.

The non-deterministic turing machine (NDTM) cannot take forever and it must reject all $x \notin L$.

For each $x \notin L$, all computations paths must say "no" in the allotted time, for the NDTM to reject.