Questions tagged [nondeterminism]
The nondeterminism tag has no usage guidance.
70 questions
0
votes
1
answer
134
views
Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?
Consider an $\mathit{NPO}$ problem $O = (X,L,f,\mathit{opt})$ according to the definition of $\mathit{NPO}$ found in this answer.
What I don't fully understand is what happens if we use a NDTM (non-...
- 11
2
votes
2
answers
604
views
Nondeterministic Turing Machines as deciders, versus NP and co-NP
While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step.
Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
- 388
1
vote
0
answers
80
views
Are there any candidate languages in NE but not E?
Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$
Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
- 11
5
votes
0
answers
133
views
"Interesting" problems in $NLogTime \cap coNLogTime$
In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape.
Criteria for "interesting" in this context:
Not in $DLogTime$: "...
- 1,234
7
votes
1
answer
409
views
Converting 2-ambiguous NFA to unambiguous NFA
This must be known, but somehow I can't locate a reference about this. Let $A$ be a nondeterministic finite automaton (NFA) over words of an alphabet $\Sigma$. I say that $A$ is unambigous if, for ...
- 9,838
3
votes
2
answers
165
views
What is formal definition of non-deterministic algorithm in context of primitive/general recursion?
I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines.
What is the reference for non-deterministic ...
- 315
-1
votes
1
answer
98
views
How is memory being used by an algorithm, to define its space complexity? [closed]
In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
- 99
3
votes
0
answers
69
views
Exponential version of $CC^0$
(In this question, "uniform" will mean $DLOGTIME$-uniform.)
In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential ...
- 1,234
0
votes
0
answers
149
views
Savitch's theorem for time complexity
Is it known that an analog of Savitch's theorem for time complexity is impossible, or is this an open question?
More formally, is $\exists d\ \forall c : \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(n^...
- 233
3
votes
1
answer
218
views
Most non-deterministic automaton
My question is about how to construct, given a number n, an NFA with n states which gets converted to a complete (i.e., with no omitted transitions) DFA with exactly $2^n$ reachable states (even ...
- 120
0
votes
0
answers
47
views
Capturing a particular regular language with $O(m)$ states
In dx.doi.org/10.1006/inco.2001.3069 the authors defined $NID_m = \{ u\in \{0,1\}^* | \exists i : u_i \neq u_{i + m} \}$ and claimed it could be recognized by a NFA of size $O(m)$. The paper mentions ...
2
votes
0
answers
86
views
Result showing that DTIME[T] is strictly contained in random-access NTIME[T]
I recall seeing a result showing that multi-tape DTIME[T] is strictly contained in random-access NTIME[T] for reasonably large T (so not the PPST proof with the $\log^\star$ sort of factors), but I ...
- 653
9
votes
1
answer
230
views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
- 5,167
16
votes
2
answers
537
views
NLOGTIME versus $\exists$DLOGTIME
$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have ...
- 18.6k
1
vote
0
answers
111
views
On proving the standard $p$-measure on $NP$ assumption?
In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from ...
- 13.3k
6
votes
1
answer
267
views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
- 119
10
votes
0
answers
188
views
Alternative proofs of Savitch's theorem?
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?
By the usual one I mean the proof based on recursively querying whether there is a midpoint.
...
- 1,479
10
votes
2
answers
663
views
Determining if a word of specific length exists that is not accepted by a NFA
It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?
Given an NFA and a ...
- 133
8
votes
1
answer
344
views
Nondeterminism is on average useless for circuits?
Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result.
Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
- 1,067
14
votes
1
answer
533
views
What are the obstructions to extending $L=SL$ to $L=NL$?
Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
- 856
0
votes
1
answer
196
views
What do stronger circuit lower bounds give in terms of derandomization?
We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.
This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
- 13.3k
19
votes
1
answer
1k
views
Example demonstrating the power of non-deterministic circuits
A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts ...
- 1,067
7
votes
1
answer
816
views
Determinism and pi-calculus
Milner embedded $\lambda$-calculus into $\pi$-calculus, showing that the $\pi$-calculus is capable of Turing-complete, deterministic calculation. Since parallel compositions of processes in the $\pi$-...
- 648
8
votes
1
answer
1k
views
NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?
Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ :
...
- 427
4
votes
1
answer
159
views
$NotTooManyP^{cc}$ class in communication complexity
Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication.
Class $NP^{cc}$ is class of languages admitting nondeterministic communication ...
- 901
10
votes
2
answers
496
views
Number of minimal DFAs of size at most $m$?
Let $\Sigma$ be an alphabet of size $2$, and consider minimal DFAs whose size is bounded by at most $m$. Let $f(m)$ denote the number of different such minimal DFAs.
Can we find a closed-form ...
- 427
3
votes
1
answer
119
views
Size bound on Büchi automaton for complement
For a given Büchi automaton $\mathcal A = (A, Q, \delta, q_0, F)$ we define a congruence on $A^{\ast}$ by
$$
\begin{array}{llll}
u \sim_{\mathcal A} v & :\Leftrightarrow & \mbox{for all }s,s' ...
- 2,057
1
vote
0
answers
229
views
Why is an automaton on finite words co-deterministic iff its transitions are co-deterministic
In the article Automata and semigroups recognizing infinite words an automaton is specified by $\mathcal A = (Q, A, E, I, F)$ where $I$ is a set of initial states and $F$ a set of final states, $Q$ ...
- 2,057
4
votes
0
answers
180
views
Nondeterministic communication complexity of Hamming distance
It is something that I think should be known:
what is nondeterministic communication complexity of following task:
is $H(x,y) \geq k$?
There is an obvious upper bound $k \log(n)$. I would expect ...
- 901
9
votes
2
answers
267
views
Is a quadratic nondeterminism speed-up of deterministic computation plausible?
This is a follow up to
nondeterministic speed-up of deterministic computation.
Is it plausible that nondeterminism (or more generally alternation)
would allow a general quadratic speed-up of ...
- 21.8k
14
votes
3
answers
611
views
Nondeterministic speed-up of deterministic computation
Can nondeterminism speed-up deterministic computation? If yes, how much?
By speeding-up deterministic computation by nondeterminism I mean results of the form:
$\mathsf{DTime}(f(n)) \subseteq \...
- 21.8k
12
votes
3
answers
488
views
Does there exist a hardest DCFL?
Greibach famously defined a language $H$, the so-called nondeterministic version of $D_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, ...
- 3,976
5
votes
0
answers
205
views
Is anything known about Sokoban with only 1 box?
This is intended to be a simpler version of my earlier question here.
In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is
the corresponding decision problem, and 1-Sokoban ...
user6973
14
votes
1
answer
668
views
How is the MA version of SETH proven to be false?
According to this paper, which discusses a nondeterministic extension of the Strong Exponential Time Hypothesis (SETH), "[…] Williams has recently shown related hypotheses about Merlin-Arthur ...
user6973
20
votes
2
answers
2k
views
Is there a non-deterministic linear time algorithm for CNF-SAT?
The decision problem CNF-SAT can be described as follows:
Input: A boolean formula $\phi$ in conjunctive normal form.
Question: Does there exist a variable assignment that satisfies $\phi$?
I'm ...
- 5,167
21
votes
3
answers
2k
views
Who introduced nondeterministic computation?
I have two historical questions:
Who first described nondeterministic computation?
I know that Cook described NP-complete problems, and
that Edmonds proposed that P algorithms are "efficient" or "...
user1338
8
votes
1
answer
389
views
Hierarchy theorem for NTIME intersect coNTIME?
$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(...
- 1,763
7
votes
0
answers
630
views
complexity of Sokoban with a small number of boxes
(I asked a very concise version of this one month ago on cs.stackexchange,
and although it got edited, it was not (otherwise) responded to.)
In this post, for positive integer values $k$, "$k$-...
user6973
27
votes
1
answer
2k
views
Deciding emptiness of intersection of regular languages in subquadratic time
Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.
Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
- 9,508
4
votes
1
answer
329
views
minimal finite automata given in-words and out-words
this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.
given: two finite sets of words $S_{in}$ and $S_{out}$. ...
- 11.1k
15
votes
2
answers
610
views
Does XOR automata (NXA) for finite languages benefit from cycles?
A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA ...
- 9,508
6
votes
1
answer
192
views
Bounds on the size of NFA for $r$-skip $k$-distinct language
This question is about an extension of a language discussed in this question.
We define the $r$-skip $k$-distinct language as follows:
$$L_{r,k}=\{\sigma_1\sigma_2\cdots \sigma_{rk}\in\Sigma^{rk} | \...
- 9,508
6
votes
1
answer
254
views
Halting time of non deterministic machine
Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever.
The Machine ...
- 1,561
5
votes
1
answer
4k
views
What are the relationship and difference between ambiguous grammars and non-deterministic ones?
Intuitively, I had assumed that ambiguous grammars were roughly the same as non-deterministic grammars. According to Wikipedia however, this is false:
there are non-deterministic unambiguous CFGs
...
- 151
8
votes
1
answer
211
views
Consequences of nondeterminism speeding up deterministic computation
If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e.
for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$,
then if follows from the deterministic ...
- 2,531
31
votes
1
answer
847
views
Can graph isomorphism be decided with square root bounded nondeterminism?
Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
- 19.2k
7
votes
2
answers
531
views
A tool for minimal NFA computation
It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$.
As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little ...
- 9,508
3
votes
0
answers
177
views
Deciding whether a binary multiplicity automaton has empty language
Multiplicity automatons (see here) is an interesting model. They have the (almost) same syntax as a non-deterministic finite automatons, but instead of deciding whether a word belongs to a language, ...
- 9,508
10
votes
1
answer
537
views
Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?
If we can prove that $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ?
I thought it is the case, but I cannot prove it (also for the converse).
- 1,130
0
votes
0
answers
206
views
How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples
Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the ...
- 73