On characterizations of the class PSPACE/poly

DOI10.1016/0304-3975(87)90111-3MaRDI QIDQ1107320zbMATH OpenOpenAlexWikidataFDO

Authors José L. Balcázar, J. Díaz, Joaquim Gabarró

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

closure propertiesKolmogorov complexityparallel computationsPSPACE/polystructural complexityvectorial straight-line programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

The class PSPACE/poly is defined as the class of sets recognizable by a deterministic Turing machine in polynomial space with the help of an advice of polynomial length. The additional information given by an advice is the same for all input words of equal length. The authors present several characterizations of the class PSPACE/poly. For instance: - as the class of languages with polynomial size quantified Boolean formulas, - the smallest class of languages containing regular languages, sparse languages, and closed under concatenation, intersection, polynomial- erasing homomorphic replication, and transitive closure of length- preserving relations, - the class of languages recognizable by polynomial size vectorial programs, - in terms of space-bounded Kolmogorov complexity sets. For vectorial straight-line programs a characterization of problems with an exponential lower bound on their nonuniform complexity is given.

Recommendations

• scientific article; zbMATH DE number 3990861
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• scientific article; zbMATH DE number 2006637
• scientific article; zbMATH DE number 5593317
• Characterizing PSPACE with pointers

Cites work

• A characterization of the power of vector machines
• A universal interconnection pattern for parallel computers
• Complexity of Presburger arithmetic with fixed quantifier dimension
• scientific article; zbMATH DE number 3829220 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3607492 (Why is no real title available?)
• scientific article; zbMATH DE number 3637282 (Why is no real title available?)
• scientific article; zbMATH DE number 1988954 (Why is no real title available?)
• On languages accepted by space-bounded oracle machines
• On similarity and duality of computation (I)
• On small generators
• On the notion of infinite pseudorandom sequences
• Polynomial Space and Transitive Closure
• Simple Representations of Certain Classes of Languages
• Vector Fortran for numerical problems on CRAY-1

Cited in

(10)

• Random languages for nonuniform complexity classes
• Logarithmic advice classes
• Characterizing PSPACE with pointers
• scientific article; zbMATH DE number 5722524 (Why is no real title available?)
• scientific article; zbMATH DE number 3990861 (Why is no real title available?)
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• scientific article; zbMATH DE number 2006637 (Why is no real title available?)
• On the computational power of discrete Hopfield nets
• Neural networks and complexity theory
• On the contribution of backward jumps to instruction sequence expressiveness

This page was built for publication: On characterizations of the class PSPACE/poly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107320)