Polynomial-time hierarchy of computable reals

File Size Format
77429_1.pdf 448Kb Adobe PDF View
Title Polynomial-time hierarchy of computable reals
Author CHEN, Qingliang; Su, Kaile; WU, Lijun
Journal Name Journal of Computational Information Systems
Year Published 2011
Place of publication United States
Publisher Binary Information Press
Abstract In mathematics, various representations of real numbers have been investigated and all these representations are proved to be mathematically equivalent. Furthermore, it is known that all effective versions of these representations lead to the same class of “computable real numbers”. However, when subrecursive (such as primitive recursive) is taken into account, these representations can lead to different notions of “computable real numbers”. This paper will look into the polynomial-time version of the problem for computable real numbers under different representations. We will summarize the known results to exhibit the comprehensive hierarchy they form. Our goal is to clarify systematically how the polynomial-time computability depends on the representations of the real numbers.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.jofcis.com/publishedpapers/2011_7_4_1108_1115.pdf
Copyright Statement Copyright 2011 Binary Information Press. The attached file is reproduced here in accordance with the copyright policy of the publisher. Please refer to the journal's website for access to the definitive, published version.
Volume 7
Issue Number 4
Page from 1108
Page to 1115
ISSN 1553-9105
Date Accessioned 2012-03-16
Date Available 2013-06-26T02:55:58Z
Language en_US
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Numerical and Computational Mathematics
URI http://hdl.handle.net/10072/44872
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1

Show simple item record

Griffith University copyright notice