I do not understand the concept of Non Deterministic Turing Machine [closed]

In a Non Deterministic Turing machine, in each branch – you do both possibilities – and only when you are done you “choose” which one is the one you need for the solution (if one exists).

For example, let’s look at the subset sum problem, with S = {a,b,c... }. The Non Deterministic Turing machine has a linear solution:

for each element:
   "guess" if it is in the subset
check if the subset has the specified sum

The tree generated will be something like that:

                                       start
                 with a                                      without a
               /         \                                   /          \
              /           \                                 /            \
             /             \                               /              \
      with b               without b                  with b              without b
      /     \               /       \                 /     \             /        \
  with c    without c    with c     without c     with c    without c    with c     without c

It is enough that one calculation (path in the tree) is correct in order for the algorithm to yield “true”. It yields “false” only if there is no such calculation.

The concept of Non Deterministic Turing Machine is purely theoretical – there is no non-deterministic turing machine available.

Bonus:

Note that everything that can be done with Non Deterministic Turing Machine – can be done with a Deterministic Turing Machine (and vise versa) – for example, the Halting Problem is not decideable in either. However, NPC problems can be done polynomially in Non Deterministic Turing Machines, and we do not know (and we assume we cannot) how to do it polynomially on Deterministic Turing Machines.

Leave a Comment

tech