New answers tagged nondeterminism
3
P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.
0
Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions.
Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice. Forking might be done by calling the operating system's fork() call (very ...
0
You can reduce from vertex cover in cubic graphs since it is known to be $\textrm{NP}$-hard. Let $G=(V,E)$ be the graph in the instance of vertex cover and, for $v \in V$, call $E_v = \{ (v,u) \mid (v,u) \in E \}$ the set of edges incident to $v$ in $G$.
Construct an instance of the exact cover problem as follows:
The elements to be covered are those in $E$...
-1
If we are saying non deterministic Turing machine and LBA are same then its wrong.
If we say non deterministic Turing machine with limited space then we can call it as LBA.
LBA has space boundaries where as Turing machine don't have.
1
Here $L$ is DCFL.
(a) $f_1(L) = \{u\in\Sigma^*: ua\in L\text{ for some }a\in\Sigma\}$ (that is, $f_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)
Let's define homomorphism $h$ as follow:
$h(a) = a, \space a\in\Sigma$
$h(\epsilon)= c$
$L' = h^{-1}(L) \cap (\Sigma^*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.)
...
Top 50 recent answers are included
