Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
np [2015/10/10 20:45]
nikolaj
np [2015/10/10 20:45] (current)
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{NP}}$ ​ (?? is this right) 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) $
Link to graph
Log In
Improvements of the human condition