MHB Non-Deterministic Selection in NPD Decider: CLIQUE

[JohnDoe2013]

Meaning of "Non-Deterministically select" in context of a Non-Deterministic Polynomial Time Decider

The following is an example from Sipser.

CLIQUE = { <G, k> : G s an undirected graph with a k-clique}

The following is a Non-Deterministic Polynomial Time Decider that decides CLIQUE:

1. Non-Deterministically select a set Q of k nodes where each node is in G.
2. Test whether G contains all edges connecting nodes in Q.
3. If yes, accept; otherwise reject.

I'm not sure what is meant by "$Non-Deterministically$ $select$".

I'm assuming it does not literally mean to just pick one of the possible branches to execute. Wikipedia says that one way of thinking about Non-Deterministic TM (NTM) is to assume that they are the "luckiest guesser". That is, they will always select a branch that leads to an accepting state (if one exists). Alternatively, it says to imagine that the NTM branches into multiple copies each of which follows one of the possible transitions.

From this I'm assuming that the NTM does not just "select a single set Q". It is basically generating one branch for each of the $\binom{n}{k}$ possible set of k-nodes and then computing each of the branches in parallel.

Can someone clarify?

 

[Evgeny.Makarov]

Hi, and welcome to the forum.

The transition function of a nondeterministic Turing machine has the type
\[
\delta:Q\times\Gamma\to \mathcal{P}(Q\times\Gamma\times\{\text{L},\text{R}\}).
\]
Here $Q$ is the set of states, $\Gamma$ is the tape alphabet, L and R direct the head to move left and right, and $\mathcal{P}(\cdot)$ denotes the powerset. That is, for each state and symbol read on the tape, the transition function returns a set of new states and symbols to write.

This is the definition, and there are two ways to interpret it. One says that for each $q\in Q$ and $a\in\Gamma$ the machine initiates a new process for each element of $\delta(q,a)$. These processes work in parallel, and each process is deterministic. The other interpretation is that the machine chooses one element of $\delta(q,a)$ and goes into that state. In the first interpretation there is only one "run" of the machine on a given input, and it consists of a tree of processes. In the second interpretation, there are multiple possible runs of the machine on a given input, and each one is the trace of a single process.

What ties these interpretation together is the definition of when the input word is accepted. Formally, this happens if there is (at least one) run that ends in the accepting state. Unfortunately, Sipser's book does not have a formal definition of acceptance for Turing machines, but it has it for nondeterministic finite automata, and the idea is quite analogous. There is a definition for TMs, for example, in the "Elements of the Theory of Computation" by Lewis and Papadimitriou, p. 222. So, we can think of an accepting computation as either a tree of deterministic processes working in parallel at least one of whom accepts, or we can think about it as a set of deterministic attempts, again at least one of whom is successful.

I'm assuming it does not literally mean to just pick one of the possible branches to execute.

This is a valid interpretation.

From this I'm assuming that the NTM does not just "select a single set Q". It is basically generating one branch for each of the $\binom{n}{k}$ possible set of k-nodes and then computing each of the branches in parallel.

This is another valid interpretation.