Sublinear-time reductions for big data computing

作     者：Gao, Xiangyu Li, Jianzhong Miao, Dongjing 

作者机构：Harbin Inst Technol Dept Comp Sci & Technol Harbin Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Dept Comp Sci & Control Engn Shenzhen Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2022年第932卷

页      面：1-12页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China (NSFC) [61832003, 61972110, U1811461, U19A2059] National Key R&D Program of China [2019YFB2101900] 

主　　题：Big data computing Sublinear-time tractability Reduction techniques Completeness 

摘      要：The inefficiency of polynomial-time (PTIME) algorithms in the context of big data indicates a departure from the traditional view on tractability. In recent years, sublineartime algorithms have been regarded as the new standard for tractability of big data computing problems. Based on the prior work on sublinear-time complexity classes[1], this paper focuses on designing appropriate reductions specialized for big data computing problems. In particular, a series of pseudo-sublinear-time reductions are proposed, and their properties are systematically investigated. It is proved thatPsTis properly contained inP, and anyPsT-complete problem and PsPLi-complete problem that is notP-complete must be a witness in P\NC. Several examples are also given to illustrate the usefulness of the proposed reductions. Then, to cope with problems that are intractable in sublinear time even after a PTIME preprocessing, the L-reduction is extended to pseudo-sublinear time. Finally, it is proved that there is noPPL-complete problem under DLOGTIME reduction. (C) 2022 Elsevier B.V. All rights reserved.