Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

8
votes
1answer
247 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 ...
13
votes
1answer
315 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 ...
0
votes
0answers
133 views

An oracle that separates BPP from PP?

Is there an oracle that gives $P=BPP\neq NP=PP$?
0
votes
1answer
184 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^\...
17
votes
1answer
532 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 ...
6
votes
1answer
263 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$-...
9
votes
1answer
426 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$ : ...
4
votes
1answer
148 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 ...
9
votes
2answers
249 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 ...
4
votes
1answer
73 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' ...
1
vote
0answers
88 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$ ...
4
votes
0answers
159 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 ...
9
votes
1answer
171 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 ...
15
votes
3answers
418 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 \...
12
votes
3answers
279 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, ...
4
votes
0answers
154 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 ...
13
votes
1answer
545 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 ...
16
votes
2answers
708 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 ...
20
votes
3answers
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 "...
8
votes
1answer
211 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}(...
7
votes
0answers
370 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$-...
23
votes
1answer
945 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 ...
4
votes
1answer
184 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}$. ...
14
votes
2answers
459 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 ...
6
votes
1answer
165 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} | \...
6
votes
1answer
229 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 ...
4
votes
1answer
3k 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 ...
8
votes
1answer
188 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 ...
30
votes
1answer
650 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 ...
7
votes
2answers
186 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 ...
3
votes
0answers
162 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
votes
1answer
291 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).
0
votes
0answers
187 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 ...
12
votes
3answers
309 views

Is there a reduction to “door and pressure plate” games that doesn't explode solution length?

This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction ...
2
votes
1answer
271 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 ...
6
votes
1answer
552 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 \{0,1\}...
3
votes
0answers
180 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 linear-...
3
votes
0answers
438 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)$? ...
32
votes
1answer
2k 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^ \...
6
votes
1answer
156 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 ...
14
votes
2answers
623 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 ...
8
votes
3answers
710 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 NP-...
10
votes
1answer
376 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
231 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 ...
6
votes
0answers
447 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 ...
4
votes
1answer
179 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 ...
6
votes
1answer
303 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 $\mathrm{TL}[\mathsf{F},\...
2
votes
1answer
228 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 ...
17
votes
5answers
1k 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 ...
27
votes
2answers
1k 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 ...