New answers tagged

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