Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions $N{C}^i\subseteq SA{C}^i\subseteq A{C}^i$ are proper in the monotone setting, for every $i\ge 1$.

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.

We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: ∙ There is a function f: 0,1* → 0,1 computable in that has circuit complexity $2^{\Omega \left(n\right)}$. ∙ ≠ co . ∙ There is no p-optimal propositional proof system. We note that a variant of the statement (either ≠ co or ∩ co contains a function $2^{\Omega \left(n\right)}$ hard on average) seems to have a bearing on the existence of good proof complexity generators. In particular, we prove that if a minor variant...

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in $2^{2^{𝒪\left(n\right)}}$ space whether the language accepted by an $n$-state non-deterministic automaton is of a star height less than a given integer $h$ (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound...

We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity...

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., ${\text{NC}}^1$ circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform ${\text{NC}}^1$.

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC1.

In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to n(log2n)2 when n goes to infinity.


In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive...

We discuss how much space is sufficient to decide whether a unary given number n is a prime. We show that O(log log n) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log n) and also in accept–ASPACE(log log n). Moreover, if the given n is...

Let ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ be the following algorithmic problem: Given a finite simplicial complex $K$ of dimension at most $k$, does there exist a (piecewise linear) embedding of $K$ into ${ℝ}^d$? Known results easily imply polynomiality of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2}$ ($k=1,2$; the case $k=1,d=2$ is graph planarity) and of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to 2k}$ for all $k\ge 3$. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{d\to d}$ and ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{(d-1)\to d}$ are undecidable for each ${}_d\ge 5$. Our main result is NP-hardness of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{2\to 4}$ and, more generally, of ${\mathrm{𝙴𝙼𝙱𝙴𝙳}}_{k\to d}$ for all $k$, $d$ with...