On characterizations of the class PSPACE/poly (Q1107320): Difference between revisions

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.