Functions computable in polynomial space
Consider nondeterministic polynomial-time Turing machine that on input x outputs a 3 x 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. (c) 2005 Elsevier Inc. All rights reserved.
polynomial space arithmetic circuits straight-line programs complexity class of functions bottleneck machines leaf languages