Abstract:
We show that the class of integer-valued functions computable by polynomial-space Turing machines is exactly the class of functions f for which there is a nondeterministic polynomial-time Turing machine with a certain order on its paths that on input x outputs a 3x3 matrix with entries from {-1,0,1} on each path such that f(x) is exactly the upper left entry in the product of all these matrices in the order of the paths. Along the way we obtain characterizations of FPSPACE in terms of arithmetic circuits and straight-line programs.