Functions computable in polynomial space

Consider nondeterministic polynomial-time Turing machine that on input x outputs a 3×3 matrix with entries from {−1, 0, 1} on each of its paths. Define the function f where f (x) is the upper left entry in the product of all these matrices (in an order of the paths to be made precise below). We show that the class of functions f computable as just described is exactly the class FPSPACE of integer-valued functions computable by polynomial-space Turing machines. Along the way we obtain characterizations of FPSPACE in terms of arithmetic circuits and straight-line programs.

Authors

• Matthias Galota
• Heribert Vollmer

Keywords

• 68Q10
• 68Q15
• 68Q05
• Polynomial space
• Complexity class of functions
• Bottleneck machines
• Leaf languages
• Arithmetic circuits
• Straight-line programs