On uniformity within NC^ 1

DOI10.1016/0022-0000(90)90022-DzbMATH Open0719.68023OpenAlexW2045583484MaRDI QIDQ2640342FDOQ2640342

Authors: David A. Mix Barrington, Howard Straubing, Neil Immerman 

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90022-d

Recommendations

• Some classes of languages in \(NC^ 1\)
• On the relative complexity of some languages in \(NC^ 1\)
• \(NC^ 1\): The automata-theoretic viewpoint
• Nondeterministic \(NC^1\) computation
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

zbMATH Keywords

regular languagesuniform complexitylow-level circuit complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• Alternation
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Title not available (Why is that?)
• Title not available (Why is that?)
• The polynomial-time hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Languages that Capture Complexity Classes
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Title not available (Why is that?)
• Parallel computation with threshold functions
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Classifying regular events in symbolic logic
• Weak Second‐Order Arithmetic and Finite Automata
• Simulation of Parallel Random Access Machines by Circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Families of recognizable sets corresponding to certain varieties of finite monoids
• An Optimal Parallel Algorithm for Formula Evaluation
• P-uniform circuit complexity
• Finite monoids and the fine structure of NC ¹
• Log Depth Circuits for Division and Related Problems
• Relational queries computable in polynomial time
• Application of model theoretic games to discrete linear orders and finite automata
• Expressibility and Parallel Complexity
• Constant Depth Reducibility
• Title not available (Why is that?)
• Superlinear lower bounds for bounded-width branching programs

Cited In (only showing first 100 items - show all)

• Linear circuits, two-variable logic and weakly blocked monoids
• Arithmetizing uniform \(NC\)
• Root finding with threshold circuits
• Reductions to graph isomorphism
• Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
• Relativizing small complexity classes and their theories
• The equivalence of theories that characterize ALogTime
• The complexity of intersecting finite automata having few final states
• Resource trade-offs in syntactically multilinear arithmetic circuits
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Parallel complexity of iterated morphisms and the arithmetic of small numbers
• Completeness results for graph isomorphism.
• Counting quantifiers, successor relations, and logarithmic space
• Model-checking hierarchical structures
• Expressibility and Nonuniform Complexity Classes
• The computational power of membrane systems under tight uniformity conditions
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
• On adaptive DLOGTIME and POLYLOGTIME reductions
• \(NC^ 1\): The automata-theoretic viewpoint
• Machines, Computations, and Universality
• Notions of locality and their logical characterizations over finite models
• Counting modulo quantifiers on finite structures
• Deciding bisimilarity is P-complete
• Lower bounds for DNF-refutations of a relativized weak pigeonhole principle
• Nondeterministic \(NC^1\) computation
• Typed monoids -- an Eilenberg-like theorem for non regular languages
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Reductions to Graph Isomorphism
• Methods for proving completeness via logical reductions
• Circuits and expressions with nonassociative gates
• The descriptive complexity approach to LOGCFL
• The complexity of computing maximal word functions
• The exact complexity of projective image matching
• Some results on uniform arithmetic circuit complexity
• Extensions of MSO and the monadic counting hierarchy
• The parallel complexity of two problems on concurrency
• Rudimentary reductions revisited
• Descriptional and Computational Complexity of Finite Automata
• Theories of arithmetics in finite models
• Context-sensitive transitive closure operators
• An optimal lower bound on the number of variables for graph identification
• Division in logspace-uniform NC
• Succinct representation, leaf languages, and projection reductions
• Extensions to Barrington's M-program model
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Regular languages in \(NC\)
• Relationships among $PL$, $\#L$, and the determinant
• The complexity of solitaire
• On the complexity of some problems on groups input as multiplication tables
• Title not available (Why is that?)
• RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
• Lower bounds against weakly-uniform threshold circuits
• On uniformity and circuit lower bounds
• Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]
• Multi-head finite automata: Data-independent versus data-dependent computations
• Lindström quantifiers and leaf language definability
• Adaptive logspace reducibility and parallel time
• First-order logics: some characterizations and closure properties
• Descriptional and computational complexity of finite automata -- a survey
• Gap-languages and log-time complexity classes
• Title not available (Why is that?)
• A characterization of definability of second-order generalized quantifiers with applications to non-definability
• The complexity of counting quantifiers on equality languages
• The invariant problem for binary string structures and the parallel complexity theory of queries
• The isomorphism conjecture for constant depth reductions
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Computing with infinitary logic
• On input read-modes of alternating Turing machines
• The expressiveness of a family of finite set languages
• Permanent does not have succinct polynomial size arithmetic circuits of constant depth
• Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
• Bounding the space in P systems with active membranes
• Lower bounds for invariant queries in logics with counting.
• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• Title not available (Why is that?)
• Generating some classes of recursive functions by superpositions of simple arithmetic functions
• A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
• First order logic, fixed point logic and linear order
• Relations among parallel and sequential computation models
• Dynamic complexity of expansion
• Circuit complexity before the dawn of the new millennium
• Circuit complexity and the expressive power of generalized first-order formulas
• Expressive power of SQL.
• The dynamic complexity of transitive closure is in DynTC\(^{0}\).
• Title not available (Why is that?)
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Dynamic complexity of the Dyck reachability
• A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
• Descriptive complexity of \#P functions: a new perspective
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• The Intersection Problem for Finite Semigroups
• A logic for constant-depth circuits
• A constant-space sequential model of computation for first-order logic
• A constant-space sequential model of computation for first-order logic
• A second-order system for polytime reasoning based on Grädel's theorem.
• Number of variables is equivalent to space
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• On the complexity of inducing categorical and quantitative association rules
• Relating polynomial time to constant depth

This page was built for publication: On uniformity within \(NC^ 1\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640342)