The nondeterminism tag has no wiki summary.
2
votes
1answer
67 views
Number of accepting path of a non deterministic automaton
I have a question that seems to me really natural and have probably already been studied. But keyword search on this site or google does not seems to help me to find any relevent paper.
I have got a ...
-1
votes
0answers
39 views
what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA? [migrated]
I saw this term "Glushkov NFA" at http://lambda-the-ultimate.org/node/2064 . Search engines are returning references to articles that use glushkov nfa, but nothing specific about the glushkov nfa ...
3
votes
1answer
147 views
How powerful are nondeterministic constant-depth circuits?
A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow ...
2
votes
0answers
129 views
Open questions about linear-time
What are some interesting open or solved-but-hard questions around problems having linear-time solutions? Ala riffle shuffles.
I'm especially curious about problems which people believe to be ...
1
vote
0answers
132 views
Nondeterministic linear time vs. the deterministic time hierarchy
How much is known about nondeterministic linear time? I'm aware that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$
Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$? ...
22
votes
1answer
408 views
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ ...
5
votes
1answer
111 views
How big is NSC^k?
It is well known that $\mathsf{NL} \subseteq \mathsf{NC} \subseteq \mathsf{P}$, both inclusions conjectured to be proper. On the other hand $\mathsf{NP} \supseteq \mathsf{P}$, also probably a proper ...
10
votes
2answers
431 views
Büchi automata with acceptance strategy
The problem
Let $A=\langle \Sigma, Q, q_0,F,\Delta\rangle$ be a Büchi automaton, recognizing a language $L\subseteq\Sigma^\omega$.
We assume that $A$ has an acceptance strategy in the following sense ...
5
votes
3answers
298 views
Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?
There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces?
Is there any known NP-Complete (or ...
8
votes
1answer
335 views
Uniform way of quantifying “branching” in nondeterministic, probabilistic, and quantum computation?
The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
-5
votes
1answer
187 views
Does a Non deterministic TM halt after the same number of steps on the same input? [closed]
Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt.
If $M$ is a deterministic TM, it will ...
5
votes
0answers
368 views
Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? [closed]
We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the ...
3
votes
1answer
133 views
Set partitioning algorithm
I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.
I have some finite set $ U $ of some distinct elements $ e_i \in U $.
I have ...
4
votes
1answer
187 views
What is an unambiguous language in the sense of Schützenberger?
I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.
In Theorem 6 (by Kamp), the fragment ...
2
votes
1answer
190 views
Simulating nondeterministic space-bounded computation using randomness
Let's suppose that a language $L \in$ NSPACE($f(n)$) where $f(n)$ is $O(\log n)$. And now let's suppose that I have a probabilistic Turing machine. Can this machine run in $O(f(n))$ space and answer ...
16
votes
5answers
460 views
Ambiguity and Logic
In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
22
votes
2answers
756 views
Conditions for NFA universality
Consider a nondeterministic finite automata $A = (Q, \Sigma, \delta, q_0, F)$, and a function $f(n)$. Additionally we define $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$.
Now lets analyze the ...
1
vote
2answers
262 views
Separation of limited nondeterminism classes?
It is interesting to find the best lower bound on the number of nondeterministic bits needed to solve satisfiability problem. Let $\beta_k P$ be the class of problems solvable by a nondeterministic ...
4
votes
1answer
212 views
On Defining Probabilistic/Nondeterministic Circuits
Assume that we are interested in deterministic circuits of size $f(n)$. Here, $n$ represents the number of inputs to the circuit.
The standard way of defining probabilistic/nondeterministic circuits ...
16
votes
1answer
255 views
Are there natural separations in the nondeterministic time hierarchy?
The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973). The theorem states that for any ...
