Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
np [2015/10/10 20:29] nikolaj |
np [2015/10/10 20:45] nikolaj |
||
|---|---|---|---|
| Line 24: | Line 24: | ||
| The set ${\bf{NP}}$ can also be defined by introducing the non-deterministic Turing machine (NDTM) which is the post-Turing machine trying several computations at once. Formally it's a machine with two transition functions $\delta_0,\delta_1$ and at any time step the configuration is doubled and both possibilities are considered. Hence computation branches exponentially in time and the machine terminates as soon as any branch returns a result. | The set ${\bf{NP}}$ can also be defined by introducing the non-deterministic Turing machine (NDTM) which is the post-Turing machine trying several computations at once. Formally it's a machine with two transition functions $\delta_0,\delta_1$ and at any time step the configuration is doubled and both possibilities are considered. Hence computation branches exponentially in time and the machine terminates as soon as any branch returns a result. | ||
| - | We define $\mathrm{\bf{NTIME}}$ exactly like $\mathrm{\bf{NTIME}}$, only with $NDTM$'s instead of $TM$'s. Then | + | We define $\mathrm{\bf{NP}}$ (?? is this right) exactly like $\mathrm{\bf{NTIME}}$, only with $NDTM$'s instead of $TM$'s. Then |
| $ \mathrm{\bf{NP}} = \bigcup_{k\in\mathbb{N}} \mathrm{\bf{NTIME}}(n^k) $ | $ \mathrm{\bf{NP}} = \bigcup_{k\in\mathbb{N}} \mathrm{\bf{NTIME}}(n^k) $ | ||
