New answers tagged nondeterminism
0
Apart from all the answers which explain the difference, I have an example which may help you get the thing they want to say.
Consider a coin toss, you either get a H or a T. If the coin toss is random, it is highly likely that out of 1000 coin tosses, 500 would be H and it is quite unlikely that 999 out of them would be H. But if the coin toss is non-...
1
There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex. Here $O(n^\omega)$ is the running time for matrix multiplication. See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038. This may or may not ...
2
If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.
1
If someone has demonstrated that $EXP=NEXP\implies NP\subseteq SUBEXP$, then that guy has unconditionally proved a long-sought separation $P^{NP}\subsetneq NEXP$.
Proof: If $EXP\neq NEXP$, then obviously, $P^{NP}\neq NEXP$.
So assuming $EXP=NEXP$, the above statement gives us $NP\subseteq SUBEXP$. We have:
$$P^{SUBEXP}=SUBEXP$$
So, $P^{NP}\subseteq ...
Top 50 recent answers are included
