今日起在论坛和大家共同学习和讨论一些计算复杂性相关的问题， 并和大家一起了解随机算法和随机计算这一今日广泛应用的算法。
计算理论要回答三个问题。第一个问题是：什么是计算？什么问题可以借助机器求解？著名的丢番图方程要求找出整系数多项式方程 a_1x_1^{n_1}+a_2x_2^{n_2}+...+a_kx_k^{n_k}=0 的整数解。希尔伯特第十问题是：是否存在一个计算过程，判定任给的一个丢番图方程是否有整数解？数学家对什么是计算这个问题颇感兴趣。从机械化的角度看，证明过程是一个寻找满足一定数学和逻辑性质的符号串，在理解这个证明时，要进行一个形式化验证过程。数学家的兴趣是证明过程在多大程度上可以机械化。二十世纪上半叶在数学基础和计算基础领域的研究最终达成了共识：计算是一个独立于任何模型的概念，所有计算模型定义的计算都是等价的。建立在这一共识基础上的可计算理论回答了第一个问题。
希尔伯特第十问题最终被年青的苏联数学家马蒂雅谢维奇于 1970 年解决，他证明了该问题的答案是否定的。若一个问题可以借助于机器求解，我们总会设法让机器代替人类解决该问题，因为与人类相比，机器的优势不言而喻。
所以第二个问题是：如何让机器求解一个可计算问题？一台专用设备可以解决某一类特定问题，一台冯·诺依曼体系架构的计算机可以通过预置一段程序来解决指定问题。无论是用专用计算设备还是通用计算设备解题，核心都是算法。算法理论研究的，正是如何让机器解决问题。尽管人类对算法的兴趣历史悠久；但作为一门理论，系统性的研究和理论突破发生在计算机出现之后。
一个著名的例子是素数分解。这是数论中一个古老问题，直到 2004 年人们才发现这个问题有高效算法 。
另一个著名的问题是图同构问题。种种迹象表明，这不是个难问题，但一直没有找到它的高效算法。巴柏在 2016 年发表了图同构问题的一个准多项式时间算法,被发现了一个错误后，巴柏在几天之后公布了一个更新。
这些例子，把我们带到了第三个问题：给定一个计算问题，解决该问题需要多少资源？这些资源包括时间、空间，但最根本的资源限制是能量。围棋机器人可以完败人类选手，但在下棋过程中，前者所消耗的总能量远大于后者。信息技术的发展迫使我们思考如何制定更公平(因而也更环保)的游戏规则。以围棋为例，游戏规则应要求博弈双方在博弈过程中的能耗差限制在一个合理的范围。能耗限制是实实在在的。
实际应用中，我们关心一个问题是否有可行算法，即它是否有一个多项式时间算法。如果一个可计算问题没有可行解，它就是一个理论上可计算但实际中不可计算的问题，我们得想其他办法。再看一个著名的问题：给定一个图，该图的一个结点覆盖是一个结点子集，图中的任何一条边都与该结点子集中的某结点关联。最小结点覆盖问题要求计算出一个图的极小的结点覆盖集。
实际中，这就是探头安装问题，我们希望用最少的探头，监控到一个楼面的所有走廊。遗憾的是，探头安装问题没有可行解。计算复杂性理论研究如何根据解决问题所消耗的资源量对问题进行分类。它试图刻画一个问题的绝对复杂性，即界定解决该问题所需的最小资源，尽管在这方面计算复杂性理论不太成功。它还希望比较不同问题对资源的相对消耗量，在这方面计算复杂性理论非常成功。计算复杂性理论的核心关注就是可行计算，为了可行性，可以在一定范围内牺牲正确性、精度、 完全自动化，甚至可以同时牺牲三者。
从能量的角度考虑像GPT这样的模型，就会发现和人类有着惊人的差距，GPT在很多方面的能力是以人类作为衡量标准的，而人类实现了很多方面比GPT这种模型更强的计算和推理能力，但消耗了小的多得多能量。每天通过吃饭摄入的能量竟能支持如此复杂的系统（包括大脑，用于感知和推理，以及身体，用于移动）运转，不能不说是一个奇迹。
