1
$\begingroup$

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)

$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$
    – usul
    Feb 17 at 3:28
  • $\begingroup$ 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. $\endgroup$ Feb 17 at 10:14
  • 1
    $\begingroup$ 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 $\endgroup$
    – Tayfun Pay
    Feb 17 at 18:56
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18 at 8:23
  • 2
    $\begingroup$ @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). $\endgroup$ Feb 21 at 17:19

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ @Damiano: Yes, you understood the misunderstanding :-) $\endgroup$ Feb 21 at 17:58
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 21 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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