如果你想找一个np完全问题的例子那么我建议你看一下3-SAT。

基本前提是你有一个合取范式的表达式，这是一种说法，你有一系列由or连接的表达式，它们都必须为真:

(a or b) and (b or !c) and (d or !e or f) ...

3- sat问题是找到一个满足表达式的解，其中每个or表达式恰好有3个布尔值可以匹配:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

这个问题的解可能是(A =T, b=T, c=F, d=F)。然而，目前还没有发现能在一般情况下在多项式时间内解决这个问题的算法。这意味着解决这个问题的最佳方法基本上是进行强力的猜测和检查，并尝试不同的组合，直到找到一个有效的组合。

3-SAT问题的特殊之处在于任何np完全问题都可以简化为3-SAT问题。这意味着如果你能找到一个多项式时间算法来解决这个问题，那么你就能得到1,000,000美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

如果你想找一个np完全问题的例子那么我建议你看一下3-SAT。

基本前提是你有一个合取范式的表达式，这是一种说法，你有一系列由or连接的表达式，它们都必须为真:

(a or b) and (b or !c) and (d or !e or f) ...

3- sat问题是找到一个满足表达式的解，其中每个or表达式恰好有3个布尔值可以匹配:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

这个问题的解可能是(A =T, b=T, c=F, d=F)。然而，目前还没有发现能在一般情况下在多项式时间内解决这个问题的算法。这意味着解决这个问题的最佳方法基本上是进行强力的猜测和检查，并尝试不同的组合，直到找到一个有效的组合。

3-SAT问题的特殊之处在于任何np完全问题都可以简化为3-SAT问题。这意味着如果你能找到一个多项式时间算法来解决这个问题，那么你就能得到1,000,000美元，更不用说全世界计算机科学家和数学家的尊重和钦佩了。

什么是NP?

NP是所有决策问题(答案是或否的问题)的集合，其中“是”答案可以通过确定性图灵机在多项式时间(O(nk)，其中n是问题大小，k是常数)验证。有时用多项式时间来定义快或快。

P是什么?

P是由确定性图灵机在多项式时间内解决的所有决策问题的集合。由于它们可以在多项式时间内求解，因此也可以在多项式时间内验证。因此P是NP的子集。

什么是np完全?

NP中的问题x也属于NP完全，当且仅当NP中的所有其他问题都可以快速地(即。在多项式时间内)转换成x。

换句话说:

x在NP中，并且 NP中的每个问题都可约为x

所以，NP完全问题的有趣之处在于，如果任何一个NP完全问题可以快速解决，那么所有NP问题都可以快速解决。

另见帖子“P=NP”是什么?为什么这是一个如此著名的问题?

什么是NP-Hard?

NP- hard是指至少和NP中最难的问题一样难的问题。注意，np完全问题也是np难的。然而，并非所有NP难问题都是NP问题(甚至是决策问题)，尽管有NP作为前缀。NP-hard中的NP并不意味着非确定性多项式时间。是的，这令人困惑，但它的用法根深蒂固，不太可能改变。

NP代表非确定性多项式时间。

这意味着使用非确定性图灵机(就像常规图灵机，但也包括非确定性“选择”函数)可以在多项式时间内解决问题。基本上，解必须在多边形时间内可测试。如果是这样的话，一个已知的NP问题可以用修改输入的给定问题来解决(一个NP问题可以简化为给定问题)，那么这个问题就是NP完全的。

从np完全问题中得到的主要东西是，它不能以任何已知的方式在多项式时间内解决。NP-Hard/NP-Complete是一种表明某些类型的问题在现实时间内无法解决的方法。

编辑:正如其他人所注意到的，np完全问题通常有近似解。在这种情况下，近似解通常给出一个近似界，用特殊的符号告诉我们这个近似有多接近。

这是一类问题，我们必须模拟每一种可能性，以确保我们有最优解。

对于一些np完全问题，有很多好的启发式方法，但它们充其量只是一个有根据的猜测。

老实说，维基百科可能是寻找答案的最佳场所。

如果NP = P，那么我们就可以比我们之前认为的更快地解决非常困难的问题。如果我们在P(多项式)时间内只解决了一个np -完全问题，那么它可以应用于np -完全范畴内的所有其他问题。