首先，我们限制函数只能输出 0 和 1，并称这样的函数为问题。因为您可以单独查询较长结果的每个位，所以这不是一个真正的限制，但它可以使理论更容易。现在我们要测量解决给定问题（计算函数）的“复杂程度”。对于数学函数f的特定机器实现M，我们总是可以计算在特定输入x上计算f所需的步数 - 这称为x在M上的运行时间。究竟什么是“步骤”，在这种情况下并不太重要。由于程序对于更大的输入旺旺需要更多的步数，而运行时间以输入的大小或长度（位数）来衡量的。这就是例如”n2 算法”的来源 -- 这就是一个当输入值大小为 n 时，至多需要n2 个步数的算法。这里的”程序”和”算法”广义上是相同的。
对于某些k，其运行时间最多为n k的程序也称为“多项式时间程序”。
复杂性理论中的两个主要问题类型是P和NP：
P是具有多项式时间程序的一类问题类 虽然 k 的指数对于一些问题来说确实非常大，但是实际上对于那些非人造的，k 不大于 4 的 P 问题仍然被认为是可以“解决的”的问题。要确认一笔
比特币的交易就是一个 P 问题，因为经过评估它需要一个多项式时间（并且只能输出 0 和 1）。简单的说就是，如果你只是计算一些值而不去“搜索”，那么这个问题就是 P 问题。但是如果你不得不搜索一些东西，那么你就会进入到另一个叫做 NP 问题的类别中。
版权申明：本内容来自于互联网，属第三方汇集推荐平台。本文的版权归原作者所有，文章言论不代表链门户的观点，链门户不承担任何法律责任。如有侵权请联系QQ：3341927519进行反馈。
