Exact formulation of definition of $NP$, in relation to $R$

Question

One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial time. There is no loops, so $P\subseteq R$.

One definition for $NP$ is having a certificate and a deterministic turing machine $N$ s.t. if $y\in B$ then there is a (polynomial size) certificate $u$ s.t. $N$ accepts $y$ and $u$ in polynomial time. What if $y\notin B$? There will be no such certificate, but are we forced to halt? Polynomial time rejection? Seems that there is no refering to this case, and it bothers me - to know what is the exact definition.

An alternative definition for $NP$ is for a language $B$ to have a non deterministic turing machine $N$ s.t. if $y\in B$ then $N$ accepts in polynomial time. What about the case $y\notin B$? Do we have any requirements? Must it halt? Polynomially? Definitions I found seem to miss it.

Having the two definitions equivalent is easy for me to see, and the problem I described is the same problem, only once for each definition.

Additionally, this problem occurs when define $NTIME$ and $NSPACE$. If the input is in the language, we will need $f(n)$ time (or space) for a non deterministic turing machine. But otherwise - if the input is not in the language - what limitations do we have, by definition, on the computation time (or space)? Must we reject? Or loop?

I am aware that classically $NP\subseteq R$ as well. Yet, this issue bothers me, so I am hoping to tidy this gap in the definitions.

Edit: I have read chi's answer in Is rejecting in polynomial time required for language to be in P? . However, I am unsatisfied with his answer, as running in some time limit $O(f(n))$ (polynomial or other) doesn't grant you a numerical upper bound on the number of steps! Say we have an input of size $n=20$ and we had $f(n)=n^2$, so the running time is $O(n^2)$, this can be any $c\cdot 400$, we can't count the number of steps and compare it to this!

Answer 1

A definition of $\mathsf{NP}$

Definition of $\mathsf{NP}$: A decision problem $prob$ (i.e., a set of input strings) is in $\mathsf{NP}$ iff there is a deterministic Turing machine (DTM) $D$ such that for each yes-instance $x$ of $prob$, there is a certificate $(x,y)$ that is accepted by $D$ in polynomial time of $|x|$.

It is notable, as described in the question, the definition above says nothing about the behavior of $D$ for a no-instance $z$ of $prob$. In particular, it is fine if $D$ does not even halt on some $(z, w)$!

An equivalent definition of $\mathsf{NP}$

However, with the definition above, we have the following.

Claim. A decision problem $prob$ is in $\mathsf{NP}$ iff there is a DTM $E$ such that for any $(x,y)$ where $x$ is an instance of $prob$, $E$ will halt in polynomial time of $|x|$ and for each yes-instance $x$ of $prob$, $E$ accepts a certificate $(x,y)$ for some $y$.
Proof.
"$\impliedby$": This is trivial.
"$\implies$": By the definition above, we have a DTM $D$ such that for each yes-instance $x$ of $prob$, there is a certificate $(x,y)$ that is accepted by $D$ in $p(|x|)$ time for some polynomial $p$.
Let us can build a new TM $E$, which on input $(x,y)$ will simulate $D$ on input $(x,y)$ for at most $p(|x|)$ steps and

• when the simulated $E$ accepts $(x,y)$ as a certificate, $E$ will accept $(x,y)$ as a certificate as well,
• otherwise, if the simulation is done, $E$ will reject.

Furthermore, we require the simulation of $s$ steps, including the check of "at most $p(|x|)$ steps" at each step, takes no more than $O(s^2)$ steps. (If you are concerned that $s^2$ may not be enough, replace it with $s^k$ with a big $k$ such as $k=2+\deg(p)$.) So, $E$ runs in polynomial time of $|x|$. $\quad\checkmark$

Corollary. $\mathsf{NP}\subseteq\mathsf{R}$
Proof. Suppose $prob\in\mathsf{NP}$. Then there is DTM $E$ such that for any $(x,y)$ where $x$ is an instance of $prob$, $E$ will halt in $p(|x|)$ time where $p(\cdot)$ is a polynomial, and for each yes-instance $x$ of $prob$, $E$ accepts a certificate $(x,y)$ for some $y$.

Let us build DTM $F$ such that upon $x$ where $x$ is an instance of $prob$, $F$ will, for every string $y$ such that $|y|\le p(|x|)$, try simulating $E$. At the end of each simulation, if the simulated $E$ accepts a certificate $(x, y)$, then $F$ accepts $x$ (and halts). If $F$ has not accepted when all simulations are done, then $F$ rejects $x$ (and halts).

Note that $F$ is a decider for $prob$. $\quad\checkmark$

Since the number of such $y$s is $2^{O(p(|x|))}$, $F$ decides $prob$ in $2^{O(p(|x|))}*p(|x|)$ time. So we have shown that $$\mathsf{NP}\subseteq\mathsf{EXPTIME}.$$

More definitions of $\mathsf{NP}$

Similarly, if we define a language $B\in \mathsf{NP}$ iff there is non-deterministic Turing machine (NDTM) $N$ such that if $y\in B$ then $N$ accepts $y$ in polynomial time and if $y\notin B$ then $N$ does not accept $y$, then for each language $B\in\mathsf{NP}$, there is a NDTM $N$ that decides $B$ in (non-deterministic) polynomial time.

Some references

The exposition above is not very formal. For example, "certificate" is not defined in formal terms here. It should be good enough as an explanation, though.

Here are a few related posts.
Formal definitions of $\mathsf{P}$ and $\mathsf{NP}$
What is EXPTIME?
What is co-something such as $\mathsf{coNP}$ and $\mathsf{coRE}$?
How to understand a class of languages as decision problems?
Is rejecting in polynomial time required for language to be in P?