Big Data Computational Complexity
The volume and veracity of big data bring significant challenges to computing. Classical computational complexity theory classifies solvable problems in polynomial time into tractable and intractable ones. However, algorithms with polynomial time complexity or even linear time complexity in big data calculations have become unacceptable in practical applications, and actually making the tractable problems recognized by the classical computational complexity theory intractable. By characterizing the complexity of tractable problems in big data computing, the classical computational complexity theory will bring some theoretically fundamental changes.