生成问题的一个解通常比验证一个给定的解时间花费要多得多?

来源：百度知道 编辑：UC知道 时间：2024/05/14 04:19:37
在一个周六的晚上，你参加了一个盛大的晚会。由于感到局促不安，你想知道这一大厅中是否有你已经认识的人。你的主人向你提议说，你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟，你就能向那里扫视，并且发现你的主人是正确的。然而，如果没有这样的暗示，你就必须环顾整个大厅，一个个地审视每一个人，看是否有你认识的人。生成问题的一个解通常比验证一个给定的解时间花费要多得多。这是这种一般现象的一个例子。与此类似的是，如果某人告诉你，数13，717，421可以写成两个较小的数的乘积，你可能不知道是否应该相信他，但是如果他告诉你它可以因子分解为3607乘上3803，那么你就可以用一个袖珍计算器容易验证这是对的。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文·考克（StephenCook）于1971年陈述的。请用数学，或逻辑学，或计算机哲学来回答，先谢谢大家了。
这是您走向知道之星的第一题，也是拿百万美金的题目，请拿出学术水平来，本人还是看得懂的。先谢谢了。

这是很基本的结论了。求比验难。
举个例子来说，RSA密码的基础就是大数分解很困难。
一个大数由两个大质数相乘得到，你有了两个质数，相乘很快能验证，但是敌人只知道一个大数，要用很长时间才能破解出两个质数。现在的量子计算机如果出线，这个问题就可以解决了。有量子算法可以很快得到这两个质数。

求解不一定比验证难，天文学家预测某年某月某日某时某分某秒有日食，就比等到那一天去验证容易得多。