什么是 "Natural" NP 完全概率？
What is a "Natural" NP-Complete prob?
我认为我对 NP-Complete、NP-Hard 等总体上有相当不错的理解，但突然间，偶然发现一些文献，我发现有人说 "natural" NP-完整的问题——明确地用这些引号。我不明白他们的意思，所以我试着 google 它——它又弹出了几次，但从来没有人费心去解释 "natural".
的意思。
有人可以向我解释一下在 "natural" 周围加上引号的上下文是什么——当他们说 "natural" NP 完全问题时是什么意思？
在 CS 理论的背景下，您经常会看到有人通过定义高度人为设计的问题来证明某些属性存在问题，而这些问题在实践中几乎没有人会遇到。比如Ladner's theorem说明如果P≠NP，那么NP[=22就有问题了=] 不在 P 中，但也不是 NP-complete，但设计的具体问题是高度人为设计的，本质上是构建的唯一目的是具有指定的 属性。主观上，这些问题被称为 "unnatural" 问题，因为该问题被发明为具有一些 属性.
"natural" 问题是主观上本身就很有趣的问题 - 通常是以前研究过的问题 - 后来证明有一些有趣的理论 属性。在这种情况下，"natural" NP-完全问题将是实践中实际出现的 NP-完全问题 - 比如说，某事例如 3-可着色性、哈密顿循环问题或布尔可满足性。
我认为我对 NP-Complete、NP-Hard 等总体上有相当不错的理解，但突然间，偶然发现一些文献，我发现有人说 "natural" NP-完整的问题——明确地用这些引号。我不明白他们的意思，所以我试着 google 它——它又弹出了几次，但从来没有人费心去解释 "natural".
的意思。有人可以向我解释一下在 "natural" 周围加上引号的上下文是什么——当他们说 "natural" NP 完全问题时是什么意思？
在 CS 理论的背景下，您经常会看到有人通过定义高度人为设计的问题来证明某些属性存在问题，而这些问题在实践中几乎没有人会遇到。比如Ladner's theorem说明如果P≠NP，那么NP[=22就有问题了=] 不在 P 中，但也不是 NP-complete，但设计的具体问题是高度人为设计的，本质上是构建的唯一目的是具有指定的 属性。主观上，这些问题被称为 "unnatural" 问题，因为该问题被发明为具有一些 属性.
"natural" 问题是主观上本身就很有趣的问题 - 通常是以前研究过的问题 - 后来证明有一些有趣的理论 属性。在这种情况下，"natural" NP-完全问题将是实践中实际出现的 NP-完全问题 - 比如说，某事例如 3-可着色性、哈密顿循环问题或布尔可满足性。