# Questions tagged [nondeterminism]

Questions about automata, formal grammars or other computation-models that specifically relate to the use of nondeterminism. Not to be confused with randomness or ambiguity!

274 questions
Filter by
Sorted by
Tagged with
325 views

### Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
361 views

### Closure of regular Language - Transition Function : Sipser Proof

I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser. I have ...
2k views

### Equivalence of NFA and DFA - proof by construction

I was looking at the construction proof showing the equivalence of NFA and DFA from Sipser's text. It started by taking number of states of DFA as $\mathcal{P}(Q)$, where $\mathcal{P}(Q)$ is the set ...
824 views

### Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
3k views

### Non-deterministic Turing machine that halts on at least one branches of computation

I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing ...
9k views

### Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
191 views

### Non-deterministic algorithm for solving figure of 8

I am struggling in trying to figure out a non-deterministic algorithm for the following problem. Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected ...
157 views

### What is prefix monotonicity?

I have a background in computer architecture and only cursory understanding of process networks. For a paper I am writing I need to understand prefix monotonicity properly. For now I have "a stream ...
160 views

### What is the state of the art in encapsulated search in functional logic programming?

I am particularly interested in solutions to the problem that encapsulated search can depend on the order of evaluation. According to [1], encapsulated search in PAKCS depends on the order of ...
315 views

### Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
190 views

### Are any problems in P known to have logarithmic-time-verifiable certificates?

Problems in NP have certificates which can be verified in polynomial time. It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time. (...
2k views

### How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$: Write a ...
1k views

### Visualizing a Non Deterministic Decider

I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization ...
929 views

### Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
97 views

### Superpolynomial time set such that SP=NSP is known?

Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer? UPDATE: It must be defined by ...
10k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
4k views

### How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
1k 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 ...
217 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 ...
7k views

### What is the difference between quantum TM and nondetermistic TM?

I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
2k views

### Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
11k 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 ...