大(dà)數據的量(volume)與質(veracity)給計(jì)算問(wèn)題帶來(lái)極大(dà)的挑戰。經典計(jì)算複雜性理(lǐ)論把一個多項式時間内可(kě)解的問(wèn)題分(fēn)爲易解（Tractable）問(wèn)題和難解（Intractable）問(wèn)題。然而，面向大(dà)數據計(jì)算中，多項式時間複雜度甚至線性時間複雜度的算法在實際應用中已變得(de)不可(kě)接受，導緻經典計(jì)算複雜性理(lǐ)論認爲的易解問(wèn)題成爲實際上的難解問(wèn)題。我們給出大(dà)數據下的易解問(wèn)題的複雜性刻畫(huà)，将從(cóng)理(lǐ)論根本對經典計(jì)算複雜性理(lǐ)論進行颠覆。

從(cóng)數據量與計(jì)算有效性間的均衡角度重新審視計(jì)算複雜性和算法理(lǐ)論成爲大(dà)數據計(jì)算的核心基礎問(wèn)題。針對傳統計(jì)算複雜性理(lǐ)論對易解性問(wèn)題的定義不适用于大(dà)數據計(jì)算，以及忽略了數據量對算法有效性和問(wèn)題易解性的影(yǐng)響的問(wèn)題，研究大(dà)數據計(jì)算的易解類複雜性理(lǐ)論，定義了大(dà)數據易解問(wèn)題之間的規約并找出了完全問(wèn)題，被國(guó)際計(jì)算機(jī)理(lǐ)論界認爲是“解決大(dà)數據計(jì)算複雜性的基礎”。