我认为我对 NP-Complete、NP-Hard 等总体上有相当不错的理解，但突然间，偶然发现了一些文献，我发现有人在说一个“自然”的 NP 完全问题——明确地与那些引号。我不明白他们的意思，所以我试着用谷歌搜索——它又出现了几次，但没有人费心解释他们所说的“自然”是什么意思。
有人可以向我解释在“自然”周围加上引号的上下文是什么 - 当他们说“自然”NP完全问题时是什么意思？
在计算机科学理论的背景下，你经常会看到有人通过定义高度人为的问题来证明某些属性存在问题，而在实践中没人会真正遇到这些问题。例如，拉德纳定理表明，如果P ≠ NP ，则NP中存在一个不在P中但也不是NP的问题完全的问题，但设计的具体问题是高度人为的，本质上是为拥有指定财产的唯一目的。这些问题主观上被称为“非自然”问题，因为该问题被发明为具有某些属性。
“自然”问题是一个主观上本身就很有趣的问题——通常是之前已经研究过的问题——后来被证明具有一些有趣的理论属性。在这种情况下，“自然”的NP完全问题将是在实践中实际出现的NP完全问题 - 例如 3-可着色性、哈密顿循环问题或布尔可满足性。