How does a non-deterministic touring machine work?

Question

I understand that they are not real, and they seem to be calculating branches when there are two options, rather than choosing one. But, for example, if I say this:

“The bijection of p vertices from graph G onto graph H is not deterministically guessed” (the context here is the graph isomorphism)

What does it mean? I understand the bijection, but it says "no deterministic guess." If he guesses, how is the algorithmic approach? How can he guarantee that he will work?

Answer 1

There are different image methods. One of them that is useful to me is the oracle model. Have you ever seen a Far Side cartoon in which there is a “miracle happened here” as one of the intermediate steps? In this version of NDTM, when you need to choose something, the oracle writes the correct version on the right side of the tape. (This is taken from Garey and Johnson, Computers and Intractability, their classic book on NP-complete problems.) You are not allowed to assume that you have the right option, but it may be the wrong one.

Therefore, when you do not deterministically guess the bijection, you get the correct bijection for your purposes, if it exists.

This is not a good basis for the algorithm, since the complexity of implementing a non-deterministic Turing machine is mainly exponential in non-deterministic states, and the algorithmic equivalent of a non-deterministic assumption is to try all possible bijections.

From a theoretical point of view, I would translate it as "If there is such a bijection, what ...". From an algorithmic point of view, find another book or another chapter of the same book, since this approach is useless for even moderately large graphs.

Answer 2

They do not, they simply illustrate the point. Basically, what they do is guess the answer and verify the correctness (deterministically). This is not guessing the response part, which is important, although it checks the correctness of the answer. This is the same as saying an arbitrary decision, right? So, for example, there are problems that require exponential time to calculate, and some of their answers can be checked at polynomial time, but some of them cannot. So, what does non-deterministic TM do, it divides these two, those that can be quickly verified from those that cannot. And then this raises a larger question, if one group of questions can be checked much faster than another, can their solutions also be generated faster? This question has not yet been answered.

Answer 3

I believe that it means "do not deterministically choose a solution," and then verify that the solution is true. Since all possible options (guesses) are tested, the solution is guaranteed.

Answer 4

The physical implementation of a non-deterministic Turing machine is a DNA computer. For example, it describes how to solve the traveling salesman problem in DNA:

• Get / create a bunch of DNA sequences, each with a length proportional to the cost of the edge on your graph, and sticky ends with sequences that uniquely identify one of the vertices to which the edge connects.

• Mix them with a DNA ligase in a large glass. They will anneal each other in sequences that represent all possible paths through the graph (ok, not very long).

• Delete all sequences in which at least one vertex is missing. To do this, select each vertex in sequence using hybridization. For example, if “ACGTACA” encodes vertex 1, select for sequences that are bound to “TGTACGA”. Then repeat this selection for each other vertex.

• Sort the remaining sequences by size using gel electrophoresis. Then the sequence is the shortest. A sequence encodes the shortest path through your schedule.