Seong-lae ChoNTM
Let r = maxq,X |δ(q,X)|. So N has at most r possible choices in each step. Possible runs of N can be organized as a tree.
IDi1i2···in = The instantaneous description of N if it choses to take choice i1 in step 1, choice i2 in step 2, and so on.
Note that the r choices after each step are not the same! At each step, there are at most r choices
Definition
Equivalent definitions
- Verifiable in a polynomial time in DTM
- Solvable in a polynomial time in NTM
Mean
An NTM is an abstract model of nondeterministic branching; it does not require physical parallel processors. A deterministic computer can simulate its branches, potentially taking exponential time. Quantum Computer describes physical parallel computing, not an implementation of NTM nondeterminism.
Quantum computing does allow for a kind of parallelism (through superposition), but it is constrained by quantum mechanics and is not equivalent to the unlimited parallelism of an NDTM. Furthermore, when a quantum computation is complete, the act of measuring the qubits to read out the result collapses their quantum state, limiting the information that can be extracted to a single outcome. This is fundamentally different from an NDTM, which, by definition, can "choose" the correct answer from among many possible computational paths.