Recognizing the tractability in big data computing

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 PPLⁱ⊊PPLⁱ⁺¹, PPL⊊PT and PDP^k+1⊊PDP^k⊊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⊆P and [Formula presented]. Finally, we show that PPL is closed under DLOGTIME reduction.