Nondeterministic \(NC^1\) computation
From MaRDI portal
Publication:1276170
DOI10.1006/jcss.1998.1588zbMath0921.68029OpenAlexW4212838967MaRDI QIDQ1276170
Heribert Vollmer, Pierre McKenzie, Hervé Caussinus, Denis Thérien
Publication date: 1998
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1998.1588
Related Items
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ Uniform derandomization from pathetic lower bounds ⋮ Dual VP classes ⋮ Processing succinct matrices and vectors ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata ⋮ Parameterised counting in logspace ⋮ Positive and negative proofs for circuits and branching programs ⋮ Complexity of regular functions ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Succinct certification of monotone circuits ⋮ Tree compression using string grammars ⋮ On the Power of Algebraic Branching Programs of Width Two ⋮ Counting paths in VPA is complete for \(\#\mathrm{NC}^1\) ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Leaf languages and string compression ⋮ On the complexity of matrix rank and rigidity ⋮ Functions computable in polynomial space ⋮ The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ The algebraic theory of Parikh automata ⋮ Cost Register Automata for Nested Words ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ On the power of algebraic branching programs of width two
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- \(NC^ 1\): The automata-theoretic viewpoint
- Some observations on the connection between counting and recursion
- On counting and approximation
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On uniform circuit complexity
- On iterated integer product
- A uniform approach to define complexity classes
- A very hard log-space counting class
- Extensions to Barrington's M-program model
- Unambiguity of circuits
- Gap-definable counting classes
- Bits and relative order from residues, space efficiently
- Recursion theoretic characterizations of complexity classes of counting functions
- Logspace and logtime leaf languages
- On uniformity within \(NC^ 1\)
- Comparing counting classes for logspace, one-way logspace, and first-order
- Finite monoids and the fine structure of NC 1
- Computing Algebraic Formulas Using a Constant Number of Registers
- An Optimal Parallel Algorithm for Formula Evaluation
- Word Problems Solvable in Logspace
- On Relating Time and Space to Size and Depth
- A Uniform Circuit Lower Bound for the Permanent
- On balanced versus unbalanced computation trees
