（每日一题）NP时间内可以被确定型图灵机求解的问题

一）P

确定性图灵机可以在多项式时间内解决的问题。

ii) NP

一般有两种定义：

1、非确定性图灵机可以在多项式时间内解决的问题；

2. 确定性图灵机可以在多项式时间内解决的问题；

目前，这两个定义被认为是等效的，第二个定义使用得更频繁，第一个定义更严格。 重要的是要注意解决问题和验证问题的解决方案之间的区别。 给定一个问题，解决它通常很难验证解决方案。 例如，要找到给定数中最大的数，验证解难度等于解难度，两者都是O(N)。 另一个例子是排序。 如果使用快速排序，验证解仍然是O(N)，但是解复杂度是O(N*lgN)。

iii) NP-

NP 中的一种特殊类型的子问题。

NP中的所有问题都可以在多项式时间内归结为问题的某个子类，这类子问题称为NP-。 因此，NP-是NP的子集。 直观地讲，它是NP问题中最难的一类子问题。 因为给定一个NP问题A，只要任意一个NP问题B可以在多项式时间内求解，那么问题A就可以在多项式时间内转化为问题B来求解，使得求解问题A仍然具有多项式复杂度。

库克定理表明 SAT 问题是一个 NP 问题，这也是发现的第一个 NP 特定问题。

通常，要证明一个特定问题A是NP-问题，需要证明这个问题比一个特定NP-问题更困难，这通常称为多项式约简（也称为变换）。 也就是说，任何 NP 问题 B 都可以在多项式时间内简化为问题 A。 需要注意的是，这里归约的方向是在多项式时间内将B归约到A，而不是将A归约到B。也就是说，证明了如果B能解，则可以通过多项式间接求解A时间变换，所以A比B更困难。

例如，按照库克的说法，如果证明A比SAT问题更难，即找到一种多项式时间约简方法将SAT转化为A来求解，那么就证明A也是NP-的。 但有趣的是，所有 NP 问题都可以在多项式时间内相互约简。 也就是说，还有一种归约方法，可以将问题A转换为SAT问题，以便在多项式时间内求解。 正是基于上述可相互转换的性质，NP问题被视为一类特殊的子问题，并独立于NP问题（类似于集合论中的A）