什么是np问题(np problem)？

这些都是可以在多项式时间内验证的决策问题。这意味着，如果我声称一个特定问题有多项式时间解，你要求我证明它。然后，我会给你一个证明，你可以很容易地验证在多项式时间。这类问题称为NP问题。注意，这里我们不是在讨论这个问题是否有多项式时间解。但我们讨论的是在多项式时间内验证给定问题的解。

要回答问题的其余部分，您首先需要了解哪些NP难问题也是NP完全问题。如果一个NP难问题属于集合NP，那么它就是NP完全问题。要属于集合NP，需要解决一个问题

（i） 一个决策问题，（ii）问题的解的数量应该是有限的，每个解应该是多项式长度的，（iii）给定一个多项式长度的解，我们应该能够说问题的答案是否是肯定的。

什么是np完全问题(np complete problem)？

这些都是NP和NP难的问题。也就是说，如果我们能解决这些问题，我们就可以解决任何其他NP问题，并且这些问题的解可以在多项式时间内得到验证。

换句话说，NP完全是一个复杂类，它表示NP中所有问题X的集合，对于这些问题，可以在多项式时间内将任何其他NP问题Y简化为X。

直觉上，这意味着如果我们知道如何快速解X，我们可以快速解Y。精确地说，如果有一个多项式时间算法f在多项式时间内将Y的实例Y转换为X的实例X=f（Y），则Y可约为X，其性质是Y的答案为是，当且仅当f（Y）的答案为是。

实例

3-SAT。这是一个问题，其中我们被赋予了一个3-子句析取（OR）的连接（ANDs），形式为

其中，每个x_vij是一个布尔变量或有限预定义列表（x_1，x_2，…x_n）中一个变量的求反。

可以证明，每个NP问题都可以简化为3-SAT。证明这一点是技术性的，需要使用NP的技术定义（基于非确定性图灵机）。这就是库克定理。

使NP完全问题变得重要的是，如果可以找到一个确定的多项式时间算法来解决其中一个问题，那么每个NP问题都可以在多项式时间内解决（一个问题来解决所有问题）。

关于np完全，你需要知道什么

• NP完全问题可以在多项式时间内用确定性算法求解。
• 要解决这个问题，必须同时解决NP和NP难问题。
• 这完全是一个决策问题。
• 例如：扫雷问题，确定一个图是否有哈密顿圈，确定布尔公式是否可满足等。

Also Read: Difference Between Deterministic And Non-deterministic Algorithms

什么是np难问题(np hard problem)？

这些问题至少和NP中最难的问题一样难。如果我们能在多项式时间内解决这些问题，我们就能解决任何可能存在的NP问题。注意，这些问题不一定是NP问题。这意味着，我们可能/可能不会在多项式时间内验证这些问题的解决方案。

直觉上，这些问题至少和NP完全问题一样难。请注意，NP难问题不一定是NP中的问题，也不一定是决策问题。

这里的精确定义是，问题X是NP难的，如果存在NP完全问题Y，那么Y在多项式时间内可约为X。

但由于任何NP完全问题都可以在多项式时间内归结为任何其他NP完全问题，因此所有NP完全问题都可以在多项式时间内归结为任何NP难问题。然后，如果一个NP难问题在多项式时间内有一个解，那么所有NP问题在多项式时间内都有一个解。

实例

停顿问题是一个NP难问题。这是一个问题，给定一个程序P和输入I，它会停止吗？这是一个决策问题，但它不在NP中。很明显，任何NP完全问题都可以归结为这个问题。再举一个例子，任何NP完全问题都是NP难问题。

关于np难问题，你们需要知道什么

• 当且仅当一个NP完全问题（如Y）在多项式时间内可化简为X时，NP难问题（如X）才可求解。
• 要解决这个问题，它必须是一个NP问题。
• 这不是一个决策问题。
• 实例包括：停止问题、顶点覆盖问题、电路可满足性问题等。

Also Read: Difference Between P And NP Problems

NP困难(np hard)和表格形式的np完全问题(np complete problem in tabular form)的区别