Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-018 | 28th March 2003 00:00

Functions Computable in Polynomial Space



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.

ISSN 1433-8092 | Imprint