computer-science - NP问题为什么这样称呼(以及NP难题和NP难题)？

Question

真的。。我本星期二要进行毕业考试，这是我永远无法理解的事情之一。
我意识到可以在多项式时间内验证NP问题的解决方案。但是，确定性与这有什么关系？
而且，如果您能向我解释NP完整和NP困难在哪里得到他们的名字，那将是很棒的(我敢肯定，我理解了他们的意思，我只是不知道他们的名字与他们的名字有什么关系是)。
抱歉，这很简单，我似乎无法理解(-:
谢谢大家!

Answer 1

P

可以在多项式时间内用确定性 Turing机器解决的所有问题的类别。

NP

可以在多项式时间内通过非确定性 Turing机器解决的所有问题的类(也可以在多项式时间内通过确定性 Turing机器进行验证。)

NP-硬

一类问题，“至少与NP中最困难的问题一样困难”。形式上，问题在于NP-Hard，如果存在一个NP-完全问题，该问题可以通过多项式时间Turing减少； (另请参见:如果可以使用带有oracle的oracle机器在多项式时间内解决该问题)。这个名字的来源很明显。

人大

NP和NP-Hard都是这类问题。关于命名，even wikipedia不确定为什么要这样命名。