举例说明算法领域的P类问题和NP类问题。为什么说现代计算机只能解决确

发布网友发布时间：2022-07-08 00:53

共1个回答

热心网友时间：2023-10-09 18:36

P:多项式时间内可以解决，太多了，如排序问题
NP:多项式时间内可以验证，如大数分解问题，随便给你一个非常大的数(该数由两个非常大的素数相乘得来)，你没法很快将其分解为两个素数的乘积，但若是把这两个素数告诉你，你可以很快的验证它是由这两个素数相乘得来（即多项式时间可验证）
上述两个概念一开始是用来描述判定问题的，后来被拓展到其他问题（如优化问题）上

现代计算机一就是冯洛伊曼结构，哪怕改成哈佛结构，也依旧只是一台图灵机，其表述能力无法超过图灵机范畴，所以只能解决确定性图灵机问题(这个名词我没听过，所以只能猜测其表示的意思)