کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10331144 686531 2005 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Functions computable in polynomial space
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Functions computable in polynomial space
چکیده انگلیسی
Consider nondeterministic polynomial-time Turing machine that on input x outputs a 3 × 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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 198, Issue 1, 10 April 2005, Pages 56-70
نویسندگان
, ,