1
$\begingroup$

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!

$\endgroup$
16
  • 1
    $\begingroup$ A language is in NP if there is a nondeterministic Turing machine that always runs in polynomial time, and has an accepting path iff the word belongs to the language. All computation paths must terminate in polynomial time. $\endgroup$ May 25 at 20:29
  • $\begingroup$ Therefore, if any computation time requires polynomial time, then both acceptance and rejection can be decided in polynomial time by using a nondeterministic TM. If that being so, what is the difference between $NP$ and $CoNP$? $\endgroup$ May 25 at 20:50
  • 1
    $\begingroup$ We have a reference post on the definitions of P, NP and coNP. $\endgroup$ May 25 at 20:51
  • $\begingroup$ Could you send me a link? I'd be glad to see if there is an addressing to what bothers me, in those definitions. $\endgroup$ May 25 at 20:59
  • 1
    $\begingroup$ Perhaps that is the core of my question: what are all the restrictions for $N$ in the case of $x\notin A$? $\endgroup$ May 26 at 7:03

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ The problem that "occurs when define $\mathsf{NTIME}$ and $\mathsf{NSPACE}$" can be dealt with similarly. $\endgroup$
    – John L.
    May 26 at 10:15
  • $\begingroup$ Just to be clear: the difference between $D$ and $E$ is that $D$'s input is some $x$ and $E$'s input is already $(x,y)$? $\endgroup$ May 26 at 10:53
  • 1
    $\begingroup$ Yes. If the input is not of the expected format, $D$ will reject. Ditto for $E$. $\endgroup$
    – John L.
    May 26 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.