可计算性和复杂性/复杂性
< 可计算性和复杂性
复杂性理论是理论计算机科学的核心领域，对整个计算机科学产生了重大影响。复杂性理论试图找出执行特定任务或解决特定问题需要多少资源（时间、空间、能量等）。它试图将问题分类到复杂性类别中，以便同一类别中的问题对解决它们所需的资源具有类似的要求。例如，属于复杂性类别的所有问题，根据定义，都有一种算法可以相对快地解决它们，即在多项式时间内解决它们。
当我们谈论解决一个特定问题时，我们可能想到判定给定输入图是否连通的问题。这个问题可以以数学方式形式化为集合，即所有连通图的集合。我们说一个算法解决问题，如果它返回是，如果输入是的成员，返回否，如果不是。在我们的例子中，解决的算法将读取某个输入图，计算某些内容，然后如果它发现输入图是连通的，就说是。这个框架的妙处在于，集合就是我们要分析的问题。
给定一个问题，自然的问题是
- 解决的最快的算法有多快？
- 解决的最佳算法需要多少空间（例如硬盘）？
- 如果我的空间不多（例如，在古老的手机上），我还能找到的算法吗？然后我仍然拥有最快的算法吗？
- 假设你有一个非常困难的问题，你就是想不出如何有效地解决它？你能证明它不能被有效地解决吗？
此页面尚未开发。