On uniformity within NC^ 1
From MaRDI portal
Recommendations
Cites work
- 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?)
- 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
- 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
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(only showing first 100 items - show all)- On the complexity of the clone membership problem
- Extensional Uniformity for Boolean Circuits
- Reachability in fixed VASS: expressiveness and lower bounds
- The Complexity of Counting Quantifiers on Equality Languages
- The complexity of solitaire
- Relationships among $PL$, $\#L$, and the determinant
- A topological approach to non-uniform complexity
- Expressive completeness for LTL with modulo counting and group quantifiers
- A recursion-theoretic characterisation of the positive polynomial-time functions
- On the complexity of some problems on groups input as multiplication tables
- scientific article; zbMATH DE number 2051828 (Why is no real title available?)
- Lower bounds against weakly-uniform threshold circuits
- On uniformity and circuit lower bounds
- Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability
- Circuit complexity of regular languages
- RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
- The complexity of the comparator circuit value problem
- scientific article; zbMATH DE number 3921320 (Why is no real title available?)
- Multi-head finite automata: Data-independent versus data-dependent computations
- Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG]
- First-order logics: some characterizations and closure properties
- Expressing uniformity via oracles
- Lindström quantifiers and leaf language definability
- Adaptive logspace reducibility and parallel time
- Descriptional and computational complexity of finite automata -- a survey
- Parameterized Parallel Computing and First-Order Logic
- The graph of multiplication is equivalent to counting
- Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts
- Gap-languages and log-time complexity classes
- scientific article; zbMATH DE number 4117877 (Why is no real title available?)
- The complexity of weakly recognizing morphisms
- A query language for NC (extended abstract)
- Some lower bounds in parameterized \(\mathrm{AC}^{0}\)
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- Where first-order and monadic second-order logic coincide
- Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\)
- The complexity of counting quantifiers on equality languages
- Formal languages and the NLP black box
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\)
- Descriptive complexity of deterministic polylogarithmic time and space
- The invariant problem for binary string structures and the parallel complexity theory of queries
- A query language for NC
- The complexity of the evaluation of complex algebra expressions
- The isomorphism conjecture for constant depth reductions
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Count-free Weisfeiler-Leman and group isomorphism
- The Ungar games
- Computing with infinitary logic
- On input read-modes of alternating Turing machines
- The expressiveness of a family of finite set languages
- Recognizing Lexicographically Smallest Words and Computing Successors in Regular Languages
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Linear circuits, two-variable logic and weakly blocked monoids
- Permanent does not have succinct polynomial size arithmetic circuits of constant depth
- Arithmetizing uniform \(NC\)
- Bounding the space in P systems with active membranes
- Root finding with threshold circuits
- Lower bounds for invariant queries in logics with counting.
- Reductions to graph isomorphism
- Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\)
- Generating some classes of recursive functions by superpositions of simple arithmetic functions
- The equivalence of theories that characterize ALogTime
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- The complexity of intersecting finite automata having few final states
- Resource trade-offs in syntactically multilinear arithmetic circuits
- Dynamic complexity of expansion
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- 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
- Expressive power of SQL.
- The dynamic complexity of transitive closure is in DynTC\(^{0}\).
- Completeness results for graph isomorphism.
- Circuit complexity and the expressive power of generalized first-order formulas
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
- Dynamic complexity of the Dyck reachability
- Descriptive complexity of \#P functions: a new perspective
- Circuit complexity before the dawn of the new millennium
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- scientific article; zbMATH DE number 7471669 (Why is no real title available?)
- A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
- Constant-Round Interactive Proof Systems for AC0[2] and NC1
- Reachability and distances under multiple changes
- Model-checking hierarchical structures
- Counting quantifiers, successor relations, and logarithmic space
- AND and/or OR: uniform polynomial-size circuits
- A logic for constant-depth circuits
- The computational power of membrane systems under tight uniformity conditions
- A constant-space sequential model of computation for first-order logic
- Expressibility and Nonuniform Complexity Classes
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- A second-order system for polytime reasoning based on Grädel's theorem.
- On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Number of variables is equivalent to space
- \(NC^ 1\): The automata-theoretic viewpoint
- A constant-space sequential model of computation for first-order logic
- The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
- 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)
