文章基本信息

标题：Functions Computable in Polynomial Space
本地全文：下载
作者：Matthias Galota ; Heribert Vollmer
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：arithmetic circuits , bottleneck machines , complexity class of functions , leaf languages , polynomial space , Straight-Line Programs