日防相穜田朋美年轻照:请问优化问题中的np难,np不完全中的np是什么意思

NP完全性问题

虽然是计算机系的学生，但自己对于什么是NP问题，什么是NPC问题也并不能很好的解答，就更不用说构造怎样的一种方式来证明一个
问题是不是NP问题了。但算法中涉及了很多这样的问题，压力之下，尽我所能弄懂了，把自己的理解记录下来。

P(Polynomial问题)。在计算机里面，对一个问题寻求一种多项式的算法是一个很好的解答。从理论上来说，如果一个问题能够有多翔
实的解法的话，就算是一个很好的算法了。这种问题总可以找到一个DTM（Deterministic Turing Machine）

NP(Nondeterministic Polynomial问题)。但是对于很多问题来说，他们找不到一个多项式的解决方法，他们只能对应一个NDTM(Nondeterministic Turing Machine）来解决。可以这样想想：对于下一步的动作，他们也不知道确切的应该怎么办，只能“尝试”很多种方案 才能够得出一个答案，这显然是很费时的，这种问题就是NP问题。

NPC(NP Complete)问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难
的问题，这种问题就是NPC问题。

一般说来，如果要证明一个问题是NPC问题的话，可以拿已经是NPC问题的一个问题经过多项式时间的变化变成所需要证明的问题，那
么索要证明的问题就是一个NPC问题了。

NPC问题是一个问题族，如果里面任意一个问题有了多项式的解，那么所有的问题都可以有多项式

NP困难: NP-hard
NP: Non-deterministic Polynomial(非确定型多项式)

NP问题: 用非确定性图灵机能在多项式时间内验证的一类问题.
NP困难问题: 若NP中的每个问题R都能多项式归约到S,则S是NP困难问题.
NP完全问题: 若NP中的每个问题R都能多项式归约到S且S是NP问题,则S是NP完全问题.
从上面定义可知,NP困难问题可以是NP完全问题,也可以不是NP完全问题.但NP完全问题一定是NP困难的.