北京时间7月4日消息，“P to NP”问题一直是世界七大数学问题之一。马萨诸塞州克莱数学研究所为此设立了特殊奖金，可以证明或驳斥这一猜想并获得100万美元的奖金。但是，如果某人能够证明P实际上等于NP，则可能根本不需要关注奖金问题，因为他可以轻松地将世界的比特币放入包中。
想把世界上的比特币放进包里？请解决“P到NP”问题
正如理论计算机科学家Scott Aaronson上周在新墨西哥州洛斯阿拉莫斯国家实验室发表演讲一样，事实证明P=NP将开启一些有趣的可能性。 P和NP的重要性主要是由于它对计算的影响。
“P”指的是计算机一直在解决的问题，从简单的两位数字增加到更复杂的任务，如浏览互联网。随着问题变得更加复杂，解决它所花费的时间随着“多项式时间”而增长，“多项式时间”是具有功率和系数（例如n2）的数。如果在n2中解决问题并使输入的大小加倍，则解决问题所需的时间将翻两番。
Aaronson幽默地说，“如果有人证明P=NP，那么他们应该做的第一件事就是挖掘2000亿美元的比特币。第二件事是解决所有其他的千禧奖。”
要理解这一点，必须理解计算机是解决问题的设备，根据计算机科学之父Alan Tling提出的原则抽象成物理计算设备可读的代码。解决问题需要大量的步骤和一定的时间。随着问题数量的增加，所需时间也会增加。
然而，在许多问题中，人们可以确定给定答案在多项式时间内是正确的，但事实上，在多项式时间内得到这个答案的可能性是开放的，也许，也许不是。这些问题被称为“不确定多项式时间”或NP问题。数独是一个难以解决的NP问题，但很容易检查结果。今天另一个重要的例子是素数的分解。目前，将大数分解为素数需要很长时间，该素数比多项式时间长，但检查答案就像将结果数相乘一样简单。事实上，这是现代加密技术的基础，它依赖于生成易于验证但难以破解的安全密钥。
中文
电话咨询
微信咨询
公众号
