<p>The comments have covered a lot of ground already. I just wanted to clarify a couple of minor points about the decider/recognizer and deterministic/nondeterministic distinctions.</p>
<hr />
<p>In the context of P vs NP (computations bounded by a polynomial), there is no difference between decidability and recognizability. Any poly-time recognizer (where a polynomial bounds only the length of an accepting branch, allowing other branches to reject or diverge) can be made into a poly-time decider by rejecting once the number of steps reaches the polynomial bound.</p>
<p>Quoting your post:</p>
<blockquote>
<p>this statement often appears as &quot;it accepts if and only if one of the branches accepts&quot;, which leaves an ambiguity as to whether we speak of recognition or decision (the statement being compatible with both options).</p>
</blockquote>
<p>Both options (deciders/recognizers) define the same class of languages.</p>
<hr />
<p>In the context of decidability vs recognizability, nondeterministic machines are no more expressive than deterministic machines. A deterministic Turing machine can simply simulate all the executions of a nondeterministic Turing machine (being careful to interleave executions in the case of recognizers).</p>
<hr />
<p>Very broadly speaking, one might say that <em>complexity</em> theorists don't talk about recognizers, and <em>computability</em> theorists don't talk about nondeterministic Turing machines.</p>

CC BY-SA 4.0
2024-02-21T17:30:53.740Z
Thanks for the answer, also useful. I accepted Damiano's answer, as it addresses exactly the points that I wanted to be clarified. Note that whether a DTM can simulate an NTM was not a concern here (this fact is pretty clear), it was rather the opposite, which depended what rejection meant concretely for an NTM.
Arnaud Casteigts
CC BY-SA 4.0
2024-02-20T23:18:46.357Z
2024-02-20T23:32:32.780Z
2024-02-20T23:32:32.780Z
Li-yao Xia
<p>As requested, I write up my comment as an answer, hoping that I correctly understood the misunderstanding :-)</p>
<p>Li-yao Xia's answer already clarifies that, in the context of complexity, there are only deciders.  In computability, &quot;not accepting&quot; and &quot;rejecting&quot; are not the same thing because of non-terminating computations.  (Incidentally, this asymmetry is why the class of recursively enumerable languages is not immediately closed under complement--and in fact this is provably not so).  But in complexity, one only considers machines terminating on every input and on every branch (in the non-deterministic case), so not accepting equals rejecting.</p>
<p>If I understand correctly, the OP is misunderstanding how non-deterministic machines collect the local decisions of their branches in order to make a global decision.  It seems to me that the OP is assuming that non-deterministic machines are able to do any sort of computation with the local decisions.  This is <em>not</em> the case.</p>
<p>First of all, the computation is not arbitrary.  For example, <span class="math-container">$\mathsf{NP}$</span> uses existential non-determinism: the global decision is the <em>disjunction</em> of the local decisions, period.  The machine cannot do anything else, in particular it cannot negate the disjunction (otherwise, <span class="math-container">$\mathsf{coNP}$</span> would be immediately equal to <span class="math-container">$\mathsf{NP}$</span>, as the OP points out).  In so-called <em>alternating Turing machines</em>, the disjunction is generalized to any propositional formula.  For example, negation of disjunction, which is the same as conjunction, gives the universal non-determinism used in the definition of <span class="math-container">$\mathsf{coNP}$</span>.</p>
<p>Second, it is misleading to think that the machine does any computation at all with the result of its local branches.  It is more accurate to think of the operation yielding the global result as happening at the &quot;meta&quot; level: the machine is not computing any disjunction (or propositional formula), <em>we</em> are.  This makes it clear that, when composing non-deterministic machines, the second machine has no access to the global result of the first machine, it only has access to the local result of each branch.  Intuitively, when a non-deterministic machine branches out, it creates two completely independent &quot;worlds&quot;, which may never communicate with each other.  The second machine picks up from where the first machine left, in <em>any</em> one of these independent worlds, without any knowledge of what happened in the others.</p>

CC BY-SA 4.0
2024-02-21T17:58:37.977Z
@Damiano: Yes, you understood the misunderstanding :-)
Arnaud Casteigts
CC BY-SA 4.0
2024-02-21T09:10:23.077Z
2024-02-26T13:18:13.290Z
2024-02-26T13:18:13.290Z
Damiano Mazza
<p>While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step.</p>
<ol>
<li><p>Deciding vs Recognizing: A Turing machine <span class="math-container">$M$</span> <em>decides</em> a language <span class="math-container">$L$</span> if whenever <span class="math-container">$s\in L$</span>, <span class="math-container">$M(s)$</span> halts and accepts, and whenever <span class="math-container">$s\notin L$</span>, it halts and rejects. Similarly, <span class="math-container">$M$</span> <em>recognizes</em> <span class="math-container">$L$</span> if whenever <span class="math-container">$s\in L$</span>, <span class="math-container">$M(s)$</span> halts and accepts, and whenever <span class="math-container">$s\notin L$</span>, it either halts and rejects, or loops forever. Recognition is weaker than decidability.</p>
</li>
<li><p>Using a TM as a decider requires, it seems, to use both accept and reject states. Sipser uses both in his definitions of TMs in [1]. Some other definitions do not use reject states (e.g. Wikipedia's), which I guess is fine for some purposes (e.g. recognition only or computation beyond decision problems).</p>
</li>
<li><p>Nondeterministic Turing machines (NTM) are supposed to generalize TMs. In particular, they should be able to <em>decide</em> languages (actually the same as TMs, if one care only about computability). In this case, I would expect that an NTM accepts if at least one of the branches accepts; and that it rejects if all the branches reject. Unfortunately, this statement often appears as &quot;it accepts if and only if one of the branches accepts&quot;, which leaves an ambiguity as to whether we speak of recognition or decision (the statement being compatible with both options).</p>
</li>
</ol>
<p>Now, here is my problem. NP and co-NP are typically defined in terms of certificates and verifiers: NP is the set of languages which admit short proofs of membership (positive certificates, verifiable in polynomial time), and co-NP is the same for negative certificates. So far, so good...</p>
<p>I wanted to give also the historical definition of NP and co-NP in terms of nondeterministic TMs (rather than certificates and verifiers). But I stumbled over the following problem: If an NTM rejects when all the branches reject, then this seems to imply NP = co-NP. Taking for example 3-coloring, each of the branches guessing a coloring and verifying it will run in polynomial time (whether the coloring is valid or not).</p>
<p>Since it is unproven (let apart unlikely) that NP = no-NP, my understanding of NTMs as deciders must be wrong. Can NTMs be deciders, and if so, how do they reject concretely?</p>
<p>What am I missing?</p>
<p>[1] Introduction to the Theory of Computing (3rd edition, definition of a TM p168)</p>

CC BY-SA 4.0
2024-02-17T03:28:47.747Z
I think everything's right up until NP=co-NP. I believe the problem with your reasoning there is that it's not allowed for a nondeterministic machine to have logic of the form "if all branches reject, then we accept the input". And this kind of logic would be required to decide e.g. if a graph is not 3-colorable, by guessing all colorings and checking them all but accepting only if all the checks fail.  To show Non-3-Colorable is in NP, you'd need an algorithm where each nondeterministic branch independently tries to prove the graph is not 3-colorable, and accept if any of them succeeds.
usul
CC BY-SA 4.0
2024-02-17T10:14:16.310Z
Agreed. So this means we cannot compose NTMs, e.g. using this NTM A from another one B that negates its output. Can you confirm? My other candidate explanation for not violating NP!=co-NP was that the NTM A only recognizes L (as opposed to deciding it). Could you please confirm that an NTM does reject explicitly when none of the branches accept? In the end, I must give the right definition: is NP the set of languages that can be *decided* by a NTM in polynomial time (without composability of the ouput), or the set languages that can be *recognized* by a NTM in polynomial time. Many thanks.
Arnaud Casteigts
CC BY-SA 4.0
2024-02-17T18:56:15.493Z
You are talking about Many-One reductions vs Turing reductions... Karp reductions vs Cook reductions... If you make a call to a NP oracle than that NP oracle recognizes it whereas a base NP machine decides it. And it is not known whether NP = CoNP but it is known that P^NP = P^CoNP
Tayfun Pay
CC BY-SA 4.0
2024-02-18T08:23:01.410Z
I am not sure whether I follow but my impression is that you are misinterpreting composability.  When composing NTMs, you compose branches, not whole computations.  Adding a negation at the end of an NTM negates the result of each branch, not the disjunction of the results.  So, from a machine deciding 3-colorability, you get a machine accepting all graphs except those such that any possible coloring is a 3-coloring.
Damiano Mazza
CC BY-SA 4.0
2024-02-18T08:27:32.597Z
The definition of NP is indeed fine with non-deterministic deciders in the sense you give: you decide $L$ when, on any instance $x$, all branches terminate and $x\in L$ iff there is an accepting branch (the other reject or do not accept, it's the same thing as long as they terminate).   You get NP by imposing the existence of a polynomial $p$ s.t. all branches are of length at most $p(|x|)$.  For coNP, it's a different story: the acceptance condition becomes that *all* branches must accept.  The general definition is that of *alternating* TM, in which states are labelled by $\land$ or $\lor$.
Damiano Mazza
CC BY-SA 4.0
2024-02-19T08:28:31.987Z
@Damiano: this helps! Indeed, I was missing the point that "when composing NTMs, you compose branches, not whole computations", I think this is the key. Please feel free to summarize your comments as an answer. It would be great if you could clarify in the answer whether (1) an NTM whose all branches rejects does rejects globally, and (2) NP can indeed be defined as the set of languages that are *decidable* by an NTM in polynomial time (as opposed to recognized only). Many thanks.
Arnaud Casteigts
CC BY-SA 4.0
2024-02-20T12:40:39.180Z
Why do you think it is unlikely that NP = co-NP? Having not found a single propositional proof system with some clear exponential lower bound rather makes it appear quite likely, doesn't it? Similarly, having not found a single polynomial-time algorithm for SAT makes P != NP seem rather plausible.
xamid
CC BY-SA 4.0
2024-02-21T17:19:04.357Z
@xamid: The consequences are believed to be unlikely. NP = co-NP would imply a collapse of the polynomial hierarchy PH to its first level (which is NP itself).
Arnaud Casteigts
<turing-machines><decidability><nondeterminism>
Nondeterministic Turing Machines as deciders, versus NP and co-NP
Arnaud Casteigts
# Nondeterministic Turing Machines as deciders, versus NP and co-NP

(Asked by: username_0 on 2024-02-16)

While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step.

1. Deciding vs Recognizing: A Turing machine $M$ *decides* a language $L$ if whenever $s\in L$, $M(s)$ halts and accepts, and whenever $s\notin L$, it halts and rejects. Similarly, $M$ *recognizes* $L$ if whenever $s\in L$, $M(s)$ halts and accepts, and whenever $s\notin L$, it either halts and rejects, or loops forever. Recognition is weaker than decidability.
2. Using a TM as a decider requires, it seems, to use both accept and reject states. Sipser uses both in his definitions of TMs in [1]. Some other definitions do not use reject states (e.g. Wikipedia's), which I guess is fine for some purposes (e.g. recognition only or computation beyond decision problems).
3. Nondeterministic Turing machines (NTM) are supposed to generalize TMs. In particular, they should be able to *decide* languages (actually the same as TMs, if one care only about computability). In this case, I would expect that an NTM accepts if at least one of the branches accepts; and that it rejects if all the branches reject. Unfortunately, this statement often appears as "it accepts if and only if one of the branches accepts", which leaves an ambiguity as to whether we speak of recognition or decision (the statement being compatible with both options).

Now, here is my problem. NP and co-NP are typically defined in terms of certificates and verifiers: NP is the set of languages which admit short proofs of membership (positive certificates, verifiable in polynomial time), and co-NP is the same for negative certificates. So far, so good...

I wanted to give also the historical definition of NP and co-NP in terms of nondeterministic TMs (rather than certificates and verifiers). But I stumbled over the following problem: If an NTM rejects when all the branches reject, then this seems to imply NP = co-NP. Taking for example 3-coloring, each of the branches guessing a coloring and verifying it will run in polynomial time (whether the coloring is valid or not).

Since it is unproven (let apart unlikely) that NP = no-NP, my understanding of NTMs as deciders must be wrong. Can NTMs be deciders, and if so, how do they reject concretely?

What am I missing?

[1] Introduction to the Theory of Computing (3rd edition, definition of a TM p168)

**Tags:** turing-machines, decidability, nondeterminism
> **Comments:**
> **username_1**: I think everything's right up until NP=co-NP. I believe the problem with your reasoning there is that it's not allowed for a nondeterministic machine to have logic of the form "if all branches reject, then we accept the input". And this kind of logic would be required to decide e.g. if a graph is not 3-colorable, by guessing all colorings and checking them all but accepting only if all the checks fail.  To show Non-3-Colorable is in NP, you'd need an algorithm where each nondeterministic branch independently tries to prove the graph is not 3-colorable, and accept if any of them succeeds.  
> **username_0**: Agreed. So this means we cannot compose NTMs, e.g. using this NTM A from another one B that negates its output. Can you confirm? My other candidate explanation for not violating NP!=co-NP was that the NTM A only recognizes L (as opposed to deciding it). Could you please confirm that an NTM does reject explicitly when none of the branches accept? In the end, I must give the right definition: is NP the set of languages that can be *decided* by a NTM in polynomial time (without composability of the ouput), or the set languages that can be *recognized* by a NTM in polynomial time. Many thanks.  
> **username_2**: You are talking about Many-One reductions vs Turing reductions... Karp reductions vs Cook reductions... If you make a call to a NP oracle than that NP oracle recognizes it whereas a base NP machine decides it. And it is not known whether NP = CoNP but it is known that P^NP = P^CoNP  
> **username_3**: I am not sure whether I follow but my impression is that you are misinterpreting composability.  When composing NTMs, you compose branches, not whole computations.  Adding a negation at the end of an NTM negates the result of each branch, not the disjunction of the results.  So, from a machine deciding 3-colorability, you get a machine accepting all graphs except those such that any possible coloring is a 3-coloring.  
> **username_3**: The definition of NP is indeed fine with non-deterministic deciders in the sense you give: you decide $L$ when, on any instance $x$, all branches terminate and $x\in L$ iff there is an accepting branch (the other reject or do not accept, it's the same thing as long as they terminate).   You get NP by imposing the existence of a polynomial $p$ s.t. all branches are of length at most $p(|x|)$.  For coNP, it's a different story: the acceptance condition becomes that *all* branches must accept.  The general definition is that of *alternating* TM, in which states are labelled by $\land$ or $\lor$.  
> **username_0**: @Damiano: this helps! Indeed, I was missing the point that "when composing NTMs, you compose branches, not whole computations", I think this is the key. Please feel free to summarize your comments as an answer. It would be great if you could clarify in the answer whether (1) an NTM whose all branches rejects does rejects globally, and (2) NP can indeed be defined as the set of languages that are *decidable* by an NTM in polynomial time (as opposed to recognized only). Many thanks.  
> **username_4**: Why do you think it is unlikely that NP = co-NP? Having not found a single propositional proof system with some clear exponential lower bound rather makes it appear quite likely, doesn't it? Similarly, having not found a single polynomial-time algorithm for SAT makes P != NP seem rather plausible.  
> **username_0**: @xamid: The consequences are believed to be unlikely. NP = co-NP would imply a collapse of the polynomial hierarchy PH to its first level (which is NP itself).  

---

## 2 answers

### Answer by username_3 on 2024-02-21. Score: 7 | Accepted answer

As requested, I write up my comment as an answer, hoping that I correctly understood the misunderstanding :-)

Li-yao Xia's answer already clarifies that, in the context of complexity, there are only deciders. In computability, "not accepting" and "rejecting" are not the same thing because of non-terminating computations. (Incidentally, this asymmetry is why the class of recursively enumerable languages is not immediately closed under complement--and in fact this is provably not so). But in complexity, one only considers machines terminating on every input and on every branch (in the non-deterministic case), so not accepting equals rejecting.

If I understand correctly, the OP is misunderstanding how non-deterministic machines collect the local decisions of their branches in order to make a global decision. It seems to me that the OP is assuming that non-deterministic machines are able to do any sort of computation with the local decisions. This is *not* the case.

First of all, the computation is not arbitrary. For example, $\mathsf{NP}$ uses existential non-determinism: the global decision is the *disjunction* of the local decisions, period. The machine cannot do anything else, in particular it cannot negate the disjunction (otherwise, $\mathsf{coNP}$ would be immediately equal to $\mathsf{NP}$, as the OP points out). In so-called *alternating Turing machines*, the disjunction is generalized to any propositional formula. For example, negation of disjunction, which is the same as conjunction, gives the universal non-determinism used in the definition of $\mathsf{coNP}$.

Second, it is misleading to think that the machine does any computation at all with the result of its local branches. It is more accurate to think of the operation yielding the global result as happening at the "meta" level: the machine is not computing any disjunction (or propositional formula), *we* are. This makes it clear that, when composing non-deterministic machines, the second machine has no access to the global result of the first machine, it only has access to the local result of each branch. Intuitively, when a non-deterministic machine branches out, it creates two completely independent "worlds", which may never communicate with each other. The second machine picks up from where the first machine left, in *any* one of these independent worlds, without any knowledge of what happened in the others.

> **Comments:**
> **username_0**: @Damiano: Yes, you understood the misunderstanding :-)  

---

### Answer by username_5 on 2024-02-20. Score: 3

The comments have covered a lot of ground already. I just wanted to clarify a couple of minor points about the decider/recognizer and deterministic/nondeterministic distinctions.

---

In the context of P vs NP (computations bounded by a polynomial), there is no difference between decidability and recognizability. Any poly-time recognizer (where a polynomial bounds only the length of an accepting branch, allowing other branches to reject or diverge) can be made into a poly-time decider by rejecting once the number of steps reaches the polynomial bound.

Quoting your post:

> this statement often appears as "it accepts if and only if one of the branches accepts", which leaves an ambiguity as to whether we speak of recognition or decision (the statement being compatible with both options).

Both options (deciders/recognizers) define the same class of languages.

---

In the context of decidability vs recognizability, nondeterministic machines are no more expressive than deterministic machines. A deterministic Turing machine can simply simulate all the executions of a nondeterministic Turing machine (being careful to interleave executions in the case of recognizers).

---

Very broadly speaking, one might say that *complexity* theorists don't talk about recognizers, and *computability* theorists don't talk about nondeterministic Turing machines.

> **Comments:**
> **username_0**: Thanks for the answer, also useful. I accepted Damiano's answer, as it addresses exactly the points that I wanted to be clarified. Note that whether a DTM can simulate an NTM was not a concern here (this fact is pretty clear), it was rather the opposite, which depended what rejection meant concretely for an NTM.  

---

