NP问题为什么这样称呼（以及NP难题和NP难题）？ [英] Why are NP problems called that way (and NP-hard and NP-complete)?

问题描述

真的。。我本星期二要进行最后一次毕业考试，这是我永远无法理解的事情之一。
我意识到可以在多项式时间内验证NP问题的解决方案。但是，确定性与这有什么关系？

如果您能向我解释NP完全和NP困难在何处得到它们的名字，那将是很棒的（我很确定我得到了他们，我只是不知道他们的名字与他们的名字有什么关系。）

很抱歉，这很琐碎，我似乎无法理解（-：

谢谢大家！

解决方案

P

所有问题的类别可以通过确定性图灵机在多项式时间内求解。

NP

可以由非确定性图灵机在多项式时间内解决的所有问题（也可以由确定性图灵机在多项式时间内进行验证。）

NP困难

一类问题，至少与NP中最困难的问题一样困难。形式上，问题在于NP-Hard，如果存在一个多项式ti的NP-complete问题我图灵化为它； （另请参见：如果可以使用带有oracle的oracle机器在多项式时间内解决该问题）。

NPC

属于NP的问题类别以及NP-Hard。关于命名，甚至Wikipedia 也不确定为什么要这样命名。 / p>

Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand. I realize that a solution for NP problem can be verfied in polynomial time. But what does determinism has to do with that?
And if you could explain me where NP-complete and NP-hard got their names, that would be great (I'm pretty sure I get the meaning of them, I just don't see what their names have to do with what they are).
Sorry if that's trivial, I just can't seem to get it (-:
Thanks all!

解决方案

P

Class of all problems which can be solved by a deterministic Turing machine in polynomial time.

NP

Class of all problems which can be solved by a non-deterministic Turing machine in polynomial time (they can also be verified by a deterministic Turing machine in polynomial time.)

NP-Hard

A class of problems which are "at least as hard as the hardest problems in NP". Formally, a problem is in NP-Hard iff there is an NP-complete problem that is polynomial time Turing-reducible to it; (also: iff it can be solved in polynomial time by an oracle machine with an oracle for the problem). It is pretty obvious where the name comes from.

NPC

The class of problems which are both NP as well as NP-Hard. Regarding the naming, even wikipedia is not sure why it's named as it is.

这篇关于NP问题为什么这样称呼（以及NP难题和NP难题）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！