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/04/10 21:59] nikolaj |
np [2015/10/10 20:45] nikolaj |
||
|---|---|---|---|
| Line 8: | Line 8: | ||
| | @#55EE55: postulate | @#55EE55: $\exists M,p.\ \forall x.\ x\in L\Leftrightarrow \exists u.\ \left(M(x,u) = 1\land \left|u\right|=p(\left|x\right|)\right) $ | | | @#55EE55: postulate | @#55EE55: $\exists M,p.\ \forall x.\ x\in L\Leftrightarrow \exists u.\ \left(M(x,u) = 1\land \left|u\right|=p(\left|x\right|)\right) $ | | ||
| - | ==== Discussion ==== | + | ----- |
| + | === Discussion === | ||
| >todo: Requirements [[Polynomial time Turing machine]] | >todo: Requirements [[Polynomial time Turing machine]] | ||
| Line 15: | Line 16: | ||
| The machine $M$ still depends on the input $x$ in a computational manner, because for $x\notin L$ it is //not allowed// for there to be //any// misleading certificate resulting in the $M(x,u) = 1$. In fact, for $x\notin L$ the machine doesn't tell you anything (the class is defined by that predicate is called ${\bf{NP}}$). If $u$ also knew if $x\notin L$, then it could just be a yes/no answer and //any// language could be decided this way. Instead, the above definition permits the interpretation $M$ to be the //verifier//. | The machine $M$ still depends on the input $x$ in a computational manner, because for $x\notin L$ it is //not allowed// for there to be //any// misleading certificate resulting in the $M(x,u) = 1$. In fact, for $x\notin L$ the machine doesn't tell you anything (the class is defined by that predicate is called ${\bf{NP}}$). If $u$ also knew if $x\notin L$, then it could just be a yes/no answer and //any// language could be decided this way. Instead, the above definition permits the interpretation $M$ to be the //verifier//. | ||
| - | === Examples === | + | == Examples == |
| A problem in $\mathrm{\bf{NP}}$ is the Boolean satisfiability problem. Finding out if a circuit, given via $x$, can be satisfied is hard. But as $u$ is allowed to be a string among the right inputs, having $M$ be the machine which tests $u$ on a given circuit which returns a positive answer if it works directly answers the initial question. | A problem in $\mathrm{\bf{NP}}$ is the Boolean satisfiability problem. Finding out if a circuit, given via $x$, can be satisfied is hard. But as $u$ is allowed to be a string among the right inputs, having $M$ be the machine which tests $u$ on a given circuit which returns a positive answer if it works directly answers the initial question. | ||
| Line 23: | 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) $ | ||
| - | ==== Parents ==== | + | |
| + | ----- | ||
| === Requirements === | === Requirements === | ||
| [[Turing machine as partial function]] | [[Turing machine as partial function]] | ||
| === Subset of === | === Subset of === | ||
| [[Bit string]] | [[Bit string]] | ||
