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, 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.

Research Areas

It has become a core in most big data computing that computational complexity and algorithm theory should be re-examed in an equilibrium approach between data volume and computational effectiveness. The definition of tractability put forward by traditional computational complexity theories is not suitable for big data calculations, and ignores the influence of algorithm effectiveness on tractability. Because Big Data Computational Complexity theory successes with identifying the tractable problems in big data computing, and finding NP problem, it is considered as the “foundation for solving the computational complexity of big data” by the international computing community.

Related Publications

Graph Algorithms: Parallelization and Scalability