On uniformity within NC^ 1
From MaRDI portal
Publication:2640342
The class \(NC^ 1\) of languages recognized by log-depth polynomial-size circuits is considered. The main goal is to study circuit complexity classes within \(NC^ 1\) in a uniform setting. It is shown that families of circuits defined by first-order formulas and a uniformity corresponding to deterministic log-time reductions are equivalent. This leads to a natural notion of uniformity for low-level circuit complexity classes. In this connection the expressive power of the first-order logic with and without the BIT pedicate is explored. New quantifiers (modular, counting, majority and group quantifiers) are also introduced to express languages in larger complexity classes. Recent results on the characterization of \(NC^ 1\) in terms of constant-width branching programs are shown to still hold true in uniform setting.
Recommendations
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A taxonomy of problems with fast parallel algorithms
- Alternation
- An Optimal Parallel Algorithm for Formula Evaluation
- Application of model theoretic games to discrete linear orders and finite automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classifying regular events in symbolic logic
- Constant Depth Reducibility
- Expressibility and Parallel Complexity
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Finite monoids and the fine structure of NC 1
- scientific article; zbMATH DE number 4028925 (Why is no real title available?)
- scientific article; zbMATH DE number 4076666 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3467028 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3287733 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Languages that Capture Complexity Classes
- Log Depth Circuits for Division and Related Problems
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Nondeterministic Space is Closed under Complementation
- On Isomorphisms and Density of NP and Other Complete Sets
- On uniform circuit complexity
- P-uniform circuit complexity
- Parallel computation with threshold functions
- Parity, circuits, and the polynomial-time hierarchy
- Relational queries computable in polynomial time
- Simulation of Parallel Random Access Machines by Circuits
- Superlinear lower bounds for bounded-width branching programs
- The polynomial-time hierarchy
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(only showing first 100 items - show all)- The complexity of solitaire
- Arithmetizing uniform NC
- Rudimentary reductions revisited
- The graph of multiplication is equivalent to counting
- The invariant problem for binary string structures and the parallel complexity theory of queries
- Regular languages in \(NC\)
- Deciding bisimilarity is P-complete
- An optimal lower bound on the number of variables for graph identification
- Extensions to Barrington's M-program model
- A constant-space sequential model of computation for first-order logic
- Succinct representation, leaf languages, and projection reductions
- Relating polynomial time to constant depth
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- Nondeterministic NC^1 computation
- On the power of built-in relations in certain classes of program schemes
- Context-sensitive transitive closure operators
- The complexity of computing maximal word functions
- On the language of primitive words
- Expressing uniformity via oracles
- Counting quantifiers, successor relations, and logarithmic space
- A query language for NC
- The complexity of the evaluation of complex algebra expressions
- Gap-languages and log-time complexity classes
- Expressive power of SQL.
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- Completeness results for graph isomorphism.
- A second-order system for polytime reasoning based on Grädel's theorem.
- Circuits and expressions with nonassociative gates
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- Multi-head finite automata: Data-independent versus data-dependent computations
- First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
- Lower bounds for invariant queries in logics with counting.
- Counting modulo quantifiers on finite structures
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On the complexity of inducing categorical and quantitative association rules
- Arithmetical definability and computational complexity
- Bounding the space in P systems with active membranes
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- On the complexity of the clone membership problem
- Dynamic complexity of expansion
- A logical characterization of constant-depth circuits over the reals
- Iterated multiplication in VTC^0
- Descriptive complexity of \#P functions: a new perspective
- A topological approach to non-uniform complexity
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- Generating some classes of recursive functions by superpositions of simple arithmetic functions
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Maintenance goals of agents in a dynamic environment: formulation and policy construction
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Descriptive complexity of deterministic polylogarithmic time and space
- Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\)
- Number of variables is equivalent to space
- Division in logspace-uniform NC
- A language-theoretical approach to descriptive complexity
- Expressive completeness for LTL with modulo counting and group quantifiers
- The complexity of the comparator circuit value problem
- First order extensions of residue classes and uniform circuit complexity
- The lower reaches of circuit uniformity
- On the locality of arb-invariant first-order formulas with modulo counting quantifiers
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Dynamic complexity of the Dyck reachability
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- The Complexity of Counting Quantifiers on Equality Languages
- Theories of arithmetics in finite models
- The complexity of intersecting finite automata having few final states
- Expressibility and Nonuniform Complexity Classes
- Indistinguishability and First-Order Logic
- A Characterization of NC k by First Order Functional Programs
- On Second-Order Monadic Groupoidal Quantifiers
- Extensional Uniformity for Boolean Circuits
- A Characterisation of NL Using Membrane Systems without Charges and Dissolution
- Descriptional and Computational Complexity of Finite Automata
- Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]
- scientific article; zbMATH DE number 3921320 (Why is no real title available?)
- Resource trade-offs in syntactically multilinear arithmetic circuits
- A logic for constant-depth circuits
- Linear circuits, two-variable logic and weakly blocked monoids
- Model-checking hierarchical structures
- scientific article; zbMATH DE number 1342210 (Why is no real title available?)
- Some results on uniform arithmetic circuit complexity
- Adaptive logspace reducibility and parallel time
- scientific article; zbMATH DE number 2051828 (Why is no real title available?)
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- Achieving new upper bounds for the hypergraph duality problem through logic
- scientific article; zbMATH DE number 4117877 (Why is no real title available?)
- Lower bounds against weakly-uniform threshold circuits
- On uniformity and circuit lower bounds
- Relationships among $PL$, $\#L$, and the determinant
- Notions of locality and their logical characterizations over finite models
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- AND and/or OR: uniform polynomial-size circuits
- Reachability and distances under multiple changes
- scientific article; zbMATH DE number 7378666 (Why is no real title available?)
- scientific article; zbMATH DE number 7471669 (Why is no real title available?)
- Parameterized Parallel Computing and First-Order Logic
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)
