On characterizations of the class PSPACE/poly

DOI10.1016/0304-3975(87)90111-3zbMath0652.68060OpenAlexW1966101287WikidataQ126472584 ScholiaQ126472584MaRDI QIDQ1107320

Josep Diaz, Joaquim Gabarró, José L. Balcázar

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(87)90111-3

zbMATH Keywords

Kolmogorov complexityclosure propertiesparallel computationsstructural complexityPSPACE/polyvectorial straight-line programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Neural networks and complexity theory, On the computational power of discrete Hopfield nets, Random languages for nonuniform complexity classes, Logarithmic advice classes, On the contribution of backward jumps to instruction sequence expressiveness

Cites Work

• On small generators
• On the notion of infinite pseudorandom sequences
• A characterization of the power of vector machines
• On languages accepted by space-bounded oracle machines
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Vector Fortran for numerical problems on CRAY-1
• On similarity and duality of computation (I)
• Polynomial Space and Transitive Closure
• A universal interconnection pattern for parallel computers
• Simple Representations of Certain Classes of Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item