Linked Questions
23 questions linked to/from Differences and relationships between randomized and nondeterministic algorithms?
149
votes
4
answers
21k
views
How can it be decidable whether $\pi$ has some sequence of digits?
We were given the following exercise.
Let
$\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$
...
- 73.4k
17
votes
9
answers
7k
views
Why NFA is called Non-deterministic?
I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple ...
- 320
28
votes
5
answers
18k
views
What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]
In many textbooks NP problems are defined as:
Set of all decision problems solvable by non deterministic algorithms in polynomial time
I couldn't understand the part "solvable by non deterministic ...
- 2,251
13
votes
4
answers
11k
views
How does a nondeterministic Turing machine work?
What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"?...
- 9,895
15
votes
4
answers
1k
views
Push Down Automatons "guess" - what does that mean?
I realize non-deterministic pushdown automata can be an improvement over deterministic ones as they can "choose" among several states and there are some context-free languages which cannot be accepted ...
- 253
6
votes
4
answers
9k
views
What is determinism in computer science?
I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number ...
- 161
15
votes
3
answers
1k
views
Why nondeterminism?
Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
- 281k
1
vote
4
answers
323
views
How is a nondeterminisitic automaton running on an input?
A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states.
Does the automaton uniformly randomly choose one out of the several ...
- 5,045
1
vote
2
answers
9k
views
DFA's with more than one initial state
( This may be related to NFAs with more than one initial state )
Consider a dfa $M$ with alphabet $\Sigma$ and states $Q$, typically also characterized by a specific initial state $q_0\in Q$. As the ...
- 315
5
votes
3
answers
2k
views
Length of the certificate in complexity classes
A nondeterministic machine trying to decide membership in a language
is presented with a hint (called a "witness" or "certificate") which
proves membership (no such witness is provided for ...
7
votes
3
answers
550
views
Why does NTIME consider the length of the longest computation?
In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:
Let $N$ be a nondeterministic Turing machine that is a ...
- 9,332
9
votes
2
answers
1k
views
motivation and idea of defining non-deterministic Turing machine
This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
- 193
2
votes
2
answers
957
views
Algorithms which are both deterministic and non-deterministic
I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms ...
- 632
2
votes
1
answer
1k
views
Can an algorithm be truly non-deterministic?
I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
- 21
4
votes
1
answer
475
views
How do non-deterministic algorithms work on current machines?
I have some questions regarding the exact nature of non-deterministic algorithms. Is it right that non-deterministic algorithms do not rely on any randomness whatsoever? In which case, this Wikipedia ...
- 113