کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331144 | 686531 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Functions computable in polynomial space
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Information and Computation - Volume 198, Issue 1, 10 April 2005, Pages 56-70
نویسندگان
Matthias Galota, Heribert Vollmer,