P 类问题指的是所有可以由一个确定型图灵机在多项式表达的时间内解决的问题。简单来说,P 类问题就是能在多项式时间内解决的问题。举个例子,冒泡排序就是 P 类问题,因为该算法的时间复杂度为 O (n²),不是指数级的。
NP 类问题
相反,NP 类问题指的是需要由一个非确定型图灵机在多项式表达的时间内解决的问题。简单来说,NP 类问题的算法比 P 类问题慢很多。著名的 NP 类问题:旅行家推销问题(TSP)。即有一个推销员,要到 n 个城市推销商品,他要找出一个包含所有 n 个城市的环路,这个环路的路径小于 a。我们知道这个问题如果单纯的用枚举法来列举的话会有 (n-1)! 种解,已经不是多项式时间的算法了 (注:阶乘的复杂度比多项式高得多)。但重要的是,如果给定一个解,我们可以在多项式时间内验证该解是否正确。
矩阵乘法广泛用于科学计算、计算机图形学和模式识别领域。因此,许多计算机科学家都在努力寻找更快的算法。甚至还出现了一些与硬件相关的特殊矩阵乘法算法,例如分布式和并行算法。施特拉森算法(Strassen algorithm)是一个计算矩阵乘法的算法,是第一个时间复杂度低于 O (n3) 的矩阵乘法算法。此外,最近还有一些研究论文提出了渐进时间复杂度更低的矩阵乘法算法。然而,最快的矩阵乘法算法尚未问世。另外,现有的算法也没有明确的渐进时间复杂度。