Functions computable in polynomial space

DOI10.1016/j.ic.2005.02.002zbMath1067.68073OpenAlexW2079995088MaRDI QIDQ1775891

Matthias Galota, Heribert Vollmer

Publication date: 4 May 2005

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.02.002

zbMATH Keywords

Arithmetic circuitsBottleneck machinesComplexity class of functionsLeaf languagesPolynomial spaceStraight-line programs

Mathematics Subject Classification ID

Related Items (3)

Processing succinct matrices and vectors ⋮ CNF and DNF succinct graph encodings ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Reducibility by algebraic projections
• A uniform approach to define complexity classes
• Succinct representation, leaf languages, and projection reductions
• Nondeterministic \(NC^1\) computation
• Polynomial Space Counting Problems
• Succinct representations of graphs
• A New Pebble Game that Characterizes Parallel Complexity Classes
• PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
• Computing Algebraic Formulas Using a Constant Number of Registers
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

This page was built for publication: Functions computable in polynomial space