真的......我本周二正在进行最后一次毕业考试,这是我无法理解的事情之一.我意识到NP问题的解决方案可以在多项式时间内得到验证.但决定论与此有何关系？
如果你能解释我NP-complete和NP-hard得到他们的名字的地方,那就太棒了(我很确定我得到了他们的意思,我只是看不出他们的名字与他们的名字有什么关系是).
对不起,如果这是微不足道的,我似乎无法得到它( - :
谢谢大家!
我见过 NP 的多种定义，但我有点困惑将其称为非确定性多项式时间。
“NP 是一组可以在非确定性多项式时间内识别的语言。”
我的理解是，普通计算机（没有随机性）无法在多项式时间内识别该语言，但是具有某种形式的非确定性（抛硬币？）的计算机可以在多项式时间内解决这个问题？
有人可以纠正我吗？你能否给我举一个例子，其中抛硬币实际上可以在多项式时间内解决问题，否则该问题将呈指数级增长？
我确实理解 NP 包括可以在多项式时间内验证的语言的定义，但我不明白如何使用非确定性来识别它们。