The program-over-monoid model of computation originates with Barrington's proof that the model captures the complexity class $\mathsf{NC^1}$. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as $\mathbf{DA}$ satisfies tameness and hence that the regular languages recognized by programs over monoids in $\mathbf{DA}$ are precisely those recognizable in the classical sense by morphisms from $\mathbf{QDA}$. Third, we show by contrast that the well studied class of monoids called $\mathbf{J}$ is not tame. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from $\mathbf{DA}$.

We prove that the reachability problem for two-dimensional vector addition systems with states is NL-complete or PSPACE-complete, depending on whether the numbers in the input are encoded in unary or binary. As a key underlying technical result, we show that, if a configuration is reachable, then there exists a witnessing path whose sequence of transitions is contained in a bounded language defined by a regular expression of pseudo-polynomially bounded length. This, in turn, enables us to prove that the lengths of minimal reachability witnesses are pseudo-polynomially bounded.

Cost register automata (CRAs) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring (N U {infinity},\min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC^1 when the semiring is (Z,+,x) or (Gamma^*,max,concat). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC^1 versus GapNC^1.

The program-over-monoid model of computation originates with Barrington's proof that it captures the complexity class NC^1. Here we make progress in understanding the subtleties of the model. First, we identify a new tameness condition on a class of monoids that entails a natural characterization of the regular languages recognizable by programs over monoids from the class. Second, we prove that the class known as DA satisfies tameness and hence that the regular languages recognized by programs over monoids in DA are precisely those recognizable in the classical sense by morphisms from QDA. Third, we show by contrast that the well studied class of monoids called J is not tame and we exhibit a regular language, recognized by a program over a monoid from J, yet not recognizable classically by morphisms from the class QJ. Finally, we exhibit a program-length-based hierarchy within the class of languages recognized by programs over monoids from DA.

The Black-Box Hypothesisstates that any property of Boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an upper bound on its circuit size. If this hypothesis is true, then P neq NP. We focus on the consequences of the hypothesis being false, showing that (under general conditions on the structure of a counterexample) it implies a non-trivial algorithm for CSAT. More specifically, we show that if there is a property F of boolean functions such that F has high sensitivity on some input function f of subexponential circuit complexity (which is a sufficient condition for F being a counterexample to the Black-Box Hypothesis), then CSAT is solvable by a subexponential-size circuit family. Moreover, if such a counterexample F is symmetric, then CSAT is in Ppoly. These results provide some evidence towards the conjecture (made in this paper) that the Black-Box Hypothesis is false if and only if CSAT is easy.

The well-quasi-ordering (i.e., a well-founded quasi-ordering such that all antichains are finite) that defines well-structured transition systems (WSTS) is shown not to be the weakest hypothesis that implies decidability of the coverability problem. We show coverability decidable for monotone transition systems that only require the absence of infinite antichains and call well behaved transitions systems (WBTS) the new strict superclass of the class of WSTS that arises. By contrast, we confirm that boundedness and termination are undecidable for WBTS under the usual hypotheses, and show that stronger monotonicity conditions can enforce decidability. Proofs are similar or even identical to existing proofs but the surprising message is that a hypothesis implicitely assumed minimal for twenty years in the theory of WSTS can meaningfully be relaxed, allowing more orderings to be handled in an abstract way. Comment: 19 pages, 3 figures

Known to be decidable since 1981, there still remains a huge gap between the best known lower and upper bounds for the reach ability problem for vector addition systems with states (VASS). Here the problem is shown PSPACE-complete in the two-dimensional case, vastly improving on the doubly exponential time bound established in 1986 by Howell, Rosier, Huynh and Yen. Cover ability and bounded ness for two-dimensional VASS are also shown PSPACE-complete, and reach ability in two-dimensional VASS and in integer VASS under unary encoding are considered.

Imposing an extensional uniformity condition on a nonuniform circuit complexity class $\mathcal{C}$ means simply intersecting $\mathcal{C}$ with a uniform class $\mathcal{L}$. By contrast, the usual intensional uniformity conditions require that a resource-bounded machine be able to exhibit the circuits in the circuit family defining $\mathcal{C}$. We say that $(\mathcal{C},\mathcal{L})$ has the uniformity duality property if the extensionally uniform class $\mathcal{C}\cap\mathcal{L}$ can be captured intensionally by means of adding so-called $\mathcal{L}$-numerical predicates to the first-order descriptive complexity apparatus describing the connection language of the circuit family defining $\mathcal{C}$. This paper exhibits positive instances and negative instances of the uniformity duality property.

We study the branching program complexity of the {\em tree evaluation problem}, introduced in \cite{BrCoMcSaWe09} as a candidate for separating \nl\ from\logcfl. The input to the problem is a rooted, balanced $d$-ary tree of height$h$, whose internal nodes are labelled with $d$-ary functions on$[k]=\{1,\ldots,k\}$, and whose leaves are labelled with elements of $[k]$.Each node obtains a value in $[k]$ equal to its $d$-ary function applied to the values of its $d$ children. The output is the value of the root. Deterministic $k$-way branching programs as related to black pebbling algorithms have been studied in \cite{BrCoMcSaWe09}. Here we introduce the notion of {\em fractional pebbling} of graphs to study non-deterministicbranching program size. We prove that this yields non-deterministic branching programs with $\Theta(k^{h/2+1})$ states solving the Boolean problem ``determine whether the root has value 1'' for binary trees - this isasymptotically better than the branching program size corresponding toblack-white pebbling. We prove upper and lower bounds on the fractionalpebbling number of $d$-ary trees, as well as a general result relating thefractional pebbling number of a graph to the black-white pebbling number. We introduce a simple semantic restriction called {\em thrifty} on $k$-way branching programs solving tree evaluation problems and show that the branchingprogram size bound of $\Theta(k^h)$ is tight (up to a constant factor) for all $h\ge 2$ for deterministic thrifty programs. We show that thenon-deterministic branching programs that correspond to fractional pebbling are thrifty as well, and that the bound of $\Theta(k^{h/2+1})$ is tight for non-deterministic thrifty programs for $h=2,3,4$. We hypothesise that thrifty branching programs are optimal among $k$-way branching programs solving the tree evaluation problem - proving this for deterministic programs would separate \lspace\ from \logcfl\, and proving it for non-deterministic programs would separate \nl\ from \logcfl.

In the interactive communication model, two parties$P_{\cal X}$and$P_{\cal Y}$possess respective private but correlated inputs$x$and$y$, and$P_{\cal Y}$wants to learn$x$from$P_{\cal X}$while minimizing the communication required for the worst possible input pair$(x,y)$. Our contribution is the analysis of four nonzero-error models in this correlated data setting. In the private coin randomized model, both players are allowed to toss coins, and$P_Y$must learn$x$with high probability for every input pair. The second and third models are similar to the first one, but the players are allowed to use a common source of randomness and to solve several independent instances of the same problem simultaneously, respectively. In the fourth model,$P_{\cal Y}$is allowed to answer incorrectly for a small fraction of the inputs. We show that one round of communication is nearly optimal for the private coin randomized model. We also prove that the last three models are equivalent and can be arbitrarily better than the original worst case deterministic model when interaction is not allowed. Finally, we show that the deterministic model and all the nonzero-error models are equivalent for a class of symmetric problems arising from several practical applications, although nonzero-error and randomization allow efficient one-way protocols.

In the interactive communication model, two distant parties possess correlated inputs such as strings of bits, and the goal is for one party to learn his interlocutor's input while minimizing the communication. Our main contribution is to analyze the power of randomization in this correlated data setting. We show that the deterministic, amortized deterministic, private coin randomized, and public coin randomized models are all equivalent for a large class of problems arising from several practical applications. Furthermore, we conjecture that the private coin randomized model and the deterministic model are equivalent for every problem, and show that a proof of this statement solves the direct-sum problem for interactive communication

This paper addresses the problems of counting proof-trees (as introduced by Venkateswaran and Tompa) and counting proof-circuits, a related but seemingly more natural question. These problems lead to a common generalization of straight-line programs which we call polynomial replacement systems {PRSs}. We contribute a classification of these systems and we investigate their complexity. Diverse problems falling within the scope of this study include, for example, counting proof-circuits and evaluating $\{\cup,+\}$-circuits over the natural numbers. A number of complexity results are obtained, including a proof that counting proof-circuits is $\numP$-complete.

Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for $\bigoplusP$, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitz’s theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts $\bigoplusLOGCFL$ and $\bigoplusL$, and several other counting classes. Finally, the known inclusions $\NP/\poly \subseteq \bigoplusP/\poly$, $\LOGCFL/\poly \subseteq \bigoplusLOGCFL/\poly$, and $\NL/\poly \subseteq \bigoplusL/\poly$, which have scattered proofs in the literature (Valiant & Vazirani 1986; Gál & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring $ \mathcal{S}$.

The Cayley group membership problem (CGM) is to input a groupoid (binary algebra) G given as a multiplication table, a subset X of G, and an element t of G, and to determine whether t can be expressed as a product of elements of X. For general groupoids CGM is P-complete, and for associative algebras (semigroups) it is NL-complete. Here we investigate CGM for particular classes of groups. The problem for general groups is in SL (symmetric log space), but any kind of hardness result seems difficult because it would require constructing the entire multiplication table of a group. We introduce the complexity class FOLL, or FO(log log n), of problems solvable by uniform polysize circuit families of unbounded fan-in and depth O(log log n). Since parity is not in FOLL, no problem in FOLL can be complete for any class containing parity, such as NC/sup 1/, L, or SL. But FOLL is not known to be contained even in SL. We show that CGM for cyclic groups is in FOLL/spl cap/L and that CGM for abelian groups is in FOLL. We then partially extend our method to solvable groups, showing that CGM for groups of constant solvability class is in FOLL and that CGM for nilpotent groups can be solved by poly-size circuits of depth O((log log n)/sup 2/). (Thus the latter problem is provably not complete for any class containing parity) We also consider the problem of testing for various properties of a group input as a table: we prove that cyclicity and nilpotency can each be tested in FOLL/spl cap/L. Finally, we examine the implications of our results for the complexity of iterated multiplication, powering, and division of integers, in the context of the recent results of Chiu, Davida, and Litow.

D. Therien and T. Wilke (1996) characterized the Until hierarchy of linear temporal logic in terms of aperiodic monoids. Here, a temporal operator able to count modulo q is introduced. Temporal logic augmented with such operators is found decidable as it is shown to express precisely the solvable regular languages. Natural hierarchies are shown to arise when modular and conventional operators are interleaved. Modular operators are then cast as special cases of more general "group" temporal operators which, added to temporal logic, allow capturing any regular language L in much the same way that the syntactic monoid of L is constructed from groups and aperiodic monoids in the sense of Krohn-Rhodes.

We prove that the tree isomorphism problem, when trees are encoded as strings, is NC/sup 1/-hard under DLOGTIME-reductions. NC/sup 1/-completeness thus follows from Buss's recent NC/sup 1/ upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete.

This paper describes the simulation of an S(n) space-bounded deterministic Turing machine by a reversible Turing machine operating in space S(n). It thus answers a question posed by C. Bennett (1989) and refutes the conjecture, made by M. Li and P. Vitanyi (1996), that any reversible simulation of an irreversible computation must obey Bennett's reversible pebble game rules.

We prove tight lower bounds, of up to n/sup /spl epsiv//, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. Monotone-NC/spl ne/monotone-P. 2. /spl forall/i/spl ges/1, monotone-NC/sup i//spl ne/monotone-NC/sup i+1/. 3. More generally: For any integer function D(n), up to n/sup /spl epsiv// (for some /spl epsiv/>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const/spl middot/D(n) (for some constant Const). Only a separation of monotone-NC/sup 1/ from monotone-NC/sup 2/ was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of-this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1. For st-connectivity, we get a tight lower bound of /spl Omega/(log/sup 2/ n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-clique function, with k/spl les/n/sup /spl epsiv//, we get a tight lower bound of /spl Omega/(k log n). Only a bound of /spl Omega/(k) was previously known.

The problem of evaluating a circuit whose wires carry values from a finite monoid M and whose gates perform the monoid operation provides a meaningful generalization to the well-studied problem of evaluating a word over M. Evaluating words over monoids is closely tied to the fine structure of the complexity class $NC^1$, and in this paper analogous ties between evaluating circuits over monoids and the structure of the complexity class P are exhibited. It is shown that circuit evaluation in the case of any nonsolvable monoid is P complete, while circuits over solvable monoids can be evaluated in $DET \subseteq NC^2$. Then the case of aperiodic monoids is completely elucidated: their circuit evaluation problems are either in $AC^0$ or L- or $NL$-complete, depending on the precise algebraic properties of the monoids. Finally, it is shown that the evaluation of circuits over the cyclic group ${\Bbb Z}_q$ for fixed $q \geq 2$ is complete for the logspace counting class $co$-$MOD_qL$, that the problem for p-groups (p a prime) is complete for $MOD_pL$, and that the more general case of nilpotent groups of exponent q belongs to the Boolean closure of $MOD_qL$.

We define the counting classes NC/sup 1/, GapNC/sup 1/ PNC/sup 1/ and C/sub =/NC/sup 1/. We prove that Boolean circuits, algebraic circuits, programs over nondeterministic finite automata, and programs over constant integer matrices yield equivalent definitions of the latter three classes. We investigate closure properties. We observe that NC/sup 1//spl sube/L and that C/sub =/NC/sup 1//spl sube/L. Then we exploit our finite automaton model and extend the padding techniques used to investigate leaf languages. Finally, we draw some consequences from the resulting body of leaf language characterizations of complexity classes, including the unconditional separation of ACC/sup 0/ from MOD-PH as well as that of TC/sup 0/ from the counting hierarchy. Moreover we obtain that dlogtime-uniformity and logspace-uniformity for AC/sup 0/ coincide if and only if the polynomial time hierarchy equals PSPACE.

The problem of testing membership in aperiodic or “group-free” transformation monoids is the natural counterpart to the well-studied membership problem in permutation groups. The class A of all finite aperiodic monoids and the class G of all finite groups are two examples of varieties , the fundamental complexity units in terms of which finite monoids are classified. The collection of all varieties V forms an infinite lattice under the inclusion ordering, with the subfamily of varieties that are contained in A forming an infinite sublattice. For each V ⊆ A , the associated problem MEMB( V ) of testing membership in transformation monoids that belong to V , is considered. Remarkably, the computational complexity of each such problem turns out to look familiar. Moreover, only five possibilities occur as V ranges over the whole aperiodic sublattice: With one family of NP-hard exceptions whose exact status is still unresolved, any such MEMB( V ) is either PSPACE-complete, NP-complete, P-complete or in AC 0 . These results thus uncover yet another surprisingly tight link between the theory of monoids and computational complexity theory.

We classify Abelian permutation group problems with respect to their parallel complexity. For such groups specified by generating permutations we show that testing membership, computing order and testing isomorphism are $NC^1 $-equivalent to (and therefore have essentially the same parallel complexity as) determining solvability of a system of linear equations modulo a product of small prime powers; we show that intersecting two such groups is $NC^1 $-equivalent to computing setwise stabilizers; we show that each of these problems is $NC^1 $-reducible to the problem of computing a generator-relator presentation. Then we prove that the aforementioned problems belong to $NC^3 $, thus identifying several natural set recognition problems in $NC$ which may lie outside $NC^2 $. Finally we prove that $NC^4 $ contains the problem of computing the cyclic decomposition of an Abelian permutation group. Background results include an $NC^1 $ solution to the problem of computing the product of n integers modulo a $\lceil {\log n} \rceil $-bit integer, and an $NC^1 $ reduction from the problem of computing a path between two nodes in a graph to that of determining accessibility of one node from another.

We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices Over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC.

We show that the permutation group membership problem can be solved in depth (logn)3 on a Monte Carlo Boolean circuit of polynomial size in the restricted case in which the group is abelian. We also show that this restricted problem is NC1-hard for NSPACE(logn).