On characterizations of the class PSPACE/poly
type: Item
instance of: scholarly article
title: On characterizations of the class PSPACE/poly
zbMATH Open document ID: 0652.68060
DOI: 10.1016/0304-3975(87)90111-3
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4064491
zbMATH Keywords: structural complexity
zbMATH Keywords: closure properties
zbMATH Keywords: parallel computations
zbMATH Keywords: PSPACE/poly
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: vectorial straight-line programs
author: José L. Balcázar
author: J. Díaz
author: Joaquim Gabarró
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90111-3
OpenAlex ID: W1966101287
cites work: Q4430281
cites work: Simple Representations of Certain Classes of Languages
cites work: Polynomial Space and Transitive Closure
cites work: On languages accepted by space-bounded oracle machines
cites work: A universal interconnection pattern for parallel computers
cites work: Q4197339
cites work: On similarity and duality of computation (I)
cites work: Q3674026
cites work: Q3862379
cites work: On the notion of infinite pseudorandom sequences
cites work: Vector Fortran for numerical problems on CRAY-1
cites work: A characterization of the power of vector machines
cites work: Q4172915
cites work: On small generators
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
Wikidata QID: Q126472584
description: scientific article; zbMATH DE number 4064491