Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOTTLENECK MACHINES:
Reports tagged with bottleneck machines:
TR03-018 | 28th March 2003
Matthias Galota, Heribert Vollmer

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 ... more >>>




ISSN 1433-8092 | Imprint