Paper Info
Title
Recognizing the tractability in big data computing.
Abstract
Due to the limitation on computational power of existing computers, the polynomial time does not work for identifying the tractable problems in big data computing. This paper adopts the sublinear time as the new standard to recognize the tractability in big data computing and study tractable problems in terms of computational complexity theory. The random-access Turing machine is used as the computational model to characterize the problems that are tractable on big data. First, pure tractable class PT is proposed and two important classes within it, PPL and PDP, are studied. The structures of this two pure tractable classes are deeply investigated and they are proved PPLi subset of PPLi+1 , PPL subset of PT and PDPk+1 subset of PDPk subset of PT. Then, pseudo-tractable class PsT is proposed and is partitioned into two classes, PsTR and PsTE, according to preprocessing techniques. The relations among pseudo-tractable classes and other complexity classes are investigated and they are proved that PsT subset of P and Pi'T-Q(0) subset of PsTR. Finally, we show that PPL is closed under DLOGTIME reduction. (C) 2020 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2020
10.1016/j.tcs.2020.07.026
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Big data computing,Tractability,Sublinear,Complexity theory
Journal
838
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Xiangyu Gao111.03
Jianzhong Li26324.23
Dongjing Miao3189.91
Xianmin Liu4125.00