We study the complexity of reachability problems on various classes of grid graphs. Reachability on certain classes of grid graphs gives natural examples of problems that are hard for NC1under AC0reductions but are not known to be hard far L; they thus give insight into the structure of L. In addition to explicating the structure of L, another of our goals is to expand the class of digraphs for which connectivity can be solved in logspace, by building on the work of Jakoby et al. (2001), who showed that reachability in series-parallel digraphs is solvable in L. We show that reachability for single-source multiple sink planar dags is solvable in L

Integer division has been known to lie in P-uniform TC/sup 0/ since the mid-1980s, and recently this was improved to L-uniform TC/sup 0/. At the time that the results in this paper were proved and submitted for conference presentation, it was unknown whether division lay in DLOGTIME-uniform TC/sup 0/ (also known as FOM). We obtain tight bounds on the uniformity required for division, by showing that division is complete for the complexity class FOM+POW obtained by augmenting FOM with a predicate for powering modulo small primes. We also show that, under a well-known number-theoretic conjecture (that there are many "smooth" primes), POW (and hence division) lies in FOM. Building on this work, Hesse has shown recently that division is in FOM [17]. The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR)-storing a number in the form of its residues modulo many small primes. The fact that CRR operations can be carried out in log space has interesting implications for small space classes. We define two versions of s(n) space for s(n)=o(log n): dspace(s(n)) as the traditional version where the worktape begins blank, and DSPACE(s(n)) where the space bound is established by endmarkers before the computation starts. We present a new translational lemma, and derive as a consequence that (for example), if one can improve the result of Hartmanis and Berman (1976) that {0/sup n/: n is prime} /spl notin/ dspace (log log n) to show that {0/sup n/: n is prime} /spl notin/ DSPACE (log log n), it would follow that L/spl ne/NP.

A language L over an alphabet A is said to have a neutral letter if there is a letter e/spl isin/A such that inserting or deleting e's from any word in A* does not change its membership (or non-membership) in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order then it is not definable in first-order. Logic with any set /spl Nscr/ of numerical predicates. We investigate this conjecture in detail, showing that it fails already for /spl Nscr/={+, *}, or possibly stronger for any set /spl Nscr/ that allows counting up to the m times iterated logarithm, 1g/sup (m)/, for any constant m. On the positive side, we prove the conjecture for the case of all monadic numerical predicates, for /spl Nscr/={+}, for the fragment BC(/spl Sigma/) of first-order logic, and for binary alphabets.

Abstract We prove that the set of properties describable by a uniform sequence of first-order sentences using at most k + 1 distinct variables is exactly equal to the set of properties checkable by a Turing machine in DSPACE[nk] (where n is the size of the universe). This set is also equal to the set of properties describable using an iterative definition for a finite set of relations of arity k. This is a refinement of the theorem PSPACE = VAR[O[1]] [8]. We suggest some directions for exploiting this result to derive trade-offs between the number of variables and the quantifier depth in descriptive complexity.

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.

In this paper we show several results about monotone planar circuits. We show that monotone planar circuits of bounded width, with access to negated input variables, compute exactly the functions in non-uniform AC/sup 0/. This provides a striking contrast to the non-planar case, where exactly NC/sup 1/ is computed. We show that the circuit value problem for monotone planar circuits, with inputs on the outerface only, can be solved in LOGDCFL/spl sube/SC, improving a LOGCFL upper bound due to Dymond and Cook. We show that for monotone planar circuits, with inputs on the outerface only, excessive depth compared to width is useless; any function computed by a monotone planar circuit of width w with inputs on the outerface can be computed by a monotone planar circuit of width O(w) and depth w/sup O(1)/. Finally, we show that monotone planar read-once circuits, with inputs on the outerface only, can be efficiently learned using membership queries.

We show that searching a width k maze is complete for Pi_k, i.e., for the k'th level of the AC0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(log log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.

Define the MOD~-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all O-1 assignments 5, F(o?) = O iff P(~= O.We obtain the unexpected result that the MOD,r,-degree of the OR of N variables is 0(~), where r is the number of distinct prime factors of m.This is optimal in the case of representation by symmetric polynomials.The MOD,, function is O if the number of input ones is a multiple of n and is 1 otherwise.We show that the MOD~-degree of both the MOD. and lMODn functions is N$)(l) exactly when there is a prime dividing n but not m.The MOD~-degree of the MOD~function is 1;we show that the MODrn,-degree of lMODm is NtiflJ if m is not a power of a prime, O(1) otherwise.A corollary is that there exists an oracle relative to which the MODm P classes (such as @P) have this structure: MODm P is closed under complement and union iff m is a prime power, and MOD.P is a subset of MODmP iff all primes dividing n also divide m.

Recently a new connection was discovered between the parallel complexity class NC 1 and the theory of finite automata in the work of Barrington on bounded width branching programs. There (nonuniform) NC 1 was characterized as those languages recognized by a certain nonuniform version of a DFA. Here we extend this characterization to show that the internal structures of NC 1 and the class of automata are closely related. In particular, using Thérien's classification of finite monoids, we give new characterizations of the classes AC 0 , depth- k AC 0 , and ACC , the last being the AC 0 closure of the mod q functions for all constant q . We settle some of the open questions in [3], give a new proof that the dot-depth hierarchy of algebraic automata theory is infinite [8], and offer a new framework for understanding the internal structure of NC 1 .

Recently a new connection was discovered between the parallel complexity class NC1 and the theory of finite automata, in the work of Barrington [Ba86] on bounded width branching programs. There (non-uniform) NC1 was characterized as those languages recognized by a certain non-uniform version of a DFA. Here we extend this characterization to show that the internal structures of NC1 and the class of automata are closely related.

Article Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 Share on Author: D A Barrington Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 1–5https://doi.org/10.1145/12130.12131Online:01 November 1986Publication History 113citation1,087DownloadsMetricsTotal Citations113Total Downloads1,087Last 12 Months19Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access