计算复杂性, 启发式算法与解析式算法
P与NP问题
计算理论的核心问题是：哪些问题可以被高效解决？哪些问题本质上是难解的？ 算法规模如何随问题规模扩展，也是计算机科学的基本原理，算法规模通过复杂度类（如P类、NP类）进行阐释：
P类问题：可以在多项式时间（如 $O(n)$ 、$O(n \log n)$ 、$O(n^2)$ ）内解决的问题（如排序、查找）；
NP类问题：可以在非确定性多项式时间（如 $O(2^n)$ ）内解决的问题（如旅行商问题、布尔 satisfiability问题）。
算法的可扩展性
多项式时间算法的执行时间随问题规模增长的速率可控，可扩展到大规模问题；
非多项式时间算法的执行时间随问题规模增长的速率爆炸，无法扩展到大规模问题。
P≠NP
复杂度类的研究揭示了问题的本质难度：例如，若P≠NP（这是计算机科学尚未解决的重大问题），则意味着NP类问题（如旅行商问题）本质上无法用多项式时间算法解决，只能通过近似算法（如贪心算法）或启发式算法（如遗传算法）处理。
启发式算法
启发式算法（Heuristic Algorithm）的核心定义是基于直观或经验构造的算法，用于在可接受的时间和空间开销内，为组合优化问题提供可行解（而非保证最优解）。其核心特征是不依赖严格的数学证明，而是通过模拟自然规律或经验规则实现高效搜索。
启发式算法与解析式算法，其区别是解释力的强度，启发式算法在一定范围还是具备现象层解释性的，只是没有解析式算法那么强而已，而不是启发式算法完全不讲理，完全无法解释，否则就不可能解决任何具体问题，这也类似物理学中的唯象理论和机制性理论。著名的唯象理论有：凝聚态物理中的平均场理论，开普勒三定律，黑体辐射的瑞利-金斯公式和维恩公式等。著名的机制性理论例如：牛顿力学、麦克斯韦方程、爱因斯坦的广义相对论、量子力学，QED，QCD等。
常见的启发式算法有：
遗传算法（模拟生物进化，通过选择、交叉、变异寻找最优解）；
模拟退火（模拟金属退火过程，以概率接受劣解，避免局部最优）；
蚁群算法（模拟蚂蚁寻路，通过信息素传递优化路径）；
神经网络（模拟生物神经元，通过训练数据学习模式）。
神经网络主要用于解决NP-hard问题（如图像识别、自然语言处理、优化调度），这些问题无法通过传统精确算法（如动态规划）在合理时间内求解，而神经网络通过经验学习（而非严格推导），能在可接受时间内给出近似最优解。
组合优化问题：例如，神经网络可用于旅行商问题（TSP）的近似求解，通过学习城市间的距离矩阵，输出近似最短路径；在 job-shop 调度问题中，神经网络可通过学习任务的优先级与时间窗口，输出近似最优调度方案。
模式识别问题：例如，卷积神经网络（CNN）通过模拟人类视觉系统的“分层处理”机制（如边缘检测、特征提取），实现对图像的分类与识别，这一过程的特征选择与权重调整均基于经验学习，而非严格数学推导。
NP完全性理论
根据NP完全性理论，若任意NP完全问题存在启发式算法，则所有NP问题都存在启发式算法——因为其他NP问题可通过归约转化为该NP完全问题，再用启发式算法求解（1971年S.A.库克与L.A.莱文独立证明SAT问题为首个NP完全问题，随后研究者通过多项式归约发现超过2000个NP完全问题，涵盖图论、组合优化等领域。M.R.加里与D.S.约翰逊的著作系统化扩展了该理论框架，为算法设计与复杂性分析奠定了基础）。
神经网络的scaling law与灵长类大脑智能
站在目前最具影响力的启发式算法-神经网络角度，因为我们发现了神经网络的scaling law，是不是可以大胆猜想，所有启发式算法可能都有对应的scaling law。
为什么会如此呢？因为我们是通过启发式算法近似求解一个NP问题，根据NP问题计算复杂度，知道NP问题本身在算法上不具备扩展性，因此当问题规模很大的时候，解析性的算法必然瘫痪，得不到有意义解，此时启发式算法就派上用场了，但是启发式算法总归不是解析解，启发式算法通过牺牲最优性（如允许2%-5%的误差），换取多项式时间内的可行解，必须依靠某一个机制来弥补问题规模很大的时候的泛化能力，缩小启发解与解析解之间的gap，scaling law或许就是这个机制，反过来，也只有能够扩展的启发式算法才具备scaling law。P类问题的算法（如Dijkstra、快速排序）旨在找到最优解，且能在多项式时间内完成（时间复杂度为 $O(n^k) $，$k$ 为常数）。例如，快速排序的时间复杂度为 $O(n \log n)$ ，无论输入规模多大，均能在可接受时间内完成，无需通过增加“模型规模”或“数据量”提升性能。
我们知道，灵长类动物大脑皮质扩张的模式，随着规模扩大而提升认知能力，这个就表明，大脑智能所运行的“算法”机制是可扩展性的，AI要产生类大脑智能也大概率应该是可扩展的启发式算法。