科学研究

大数据计算复杂性理论

研究简介

大数据的量(volume)与质(veracity)给计算问题带来极大的挑战。经典计算复杂性理论把一个多项式时间内可解的问题分为易解(Tractable)问题和难解(Intractable)问题。然而,面向大数据计算中,多项式时间复杂度甚至线性时间复杂度的算法在实际应用中已变得不可接受,导致经典计算复杂性理论认为的易解问题成为实际上的难解问题。我们给出大数据下的易解问题的复杂性刻画,将从理论根本对经典计算复杂性理论进行颠覆。

研究领域

从数据量与计算有效性间的均衡角度重新审视计算复杂性和算法理论成为大数据计算的核心基础问题。针对传统计算复杂性理论对易解性问题的定义不适用于大数据计算,以及忽略了数据量对算法有效性和问题易解性的影响的问题,研究大数据计算的易解类复杂性理论,定义了大数据易解问题之间的规约并找出了完全问题,被国际计算机理论界认为是“解决大数据计算复杂性的基础”。
最新相关发表