从 NP-Complete 的维基百科条目中得到的信息:
“证明某个新问题是 NP-完全问题的最简单方法是首先证明它在 NP 中,然后将一些已知的 NP-完全问题归约到该问题。”
我很确定我理解了这个概念:如果我有一个问题,我可以通过以下步骤展示它是 NP-完全问题:
1.展示它在 NP 中(问题的解可以在非确定性图灵机上以多项式时间验证); 2.展示一个已知为 NP-完全问题可以被“归约”为新问题。
那么我的问题是,第一个 NP-完全问题是如何被“证明”是 NP-完全的?曾经,已知的 NP-完全问题集合可能为零,这将使得无法使用上述过程中的步骤 2。
这让我想到是否存在另一种我不知道的证明方法。或者,由于缺乏已知的多项式时间解决方案,对于某些问题,整个 NP-完全属性可能被“假定”。(事实上,写下这篇翻译后,我不会感到惊讶,但我希望得到一些大师的反馈)。
“证明某个新问题是 NP-完全问题的最简单方法是首先证明它在 NP 中,然后将一些已知的 NP-完全问题归约到该问题。”
我很确定我理解了这个概念:如果我有一个问题,我可以通过以下步骤展示它是 NP-完全问题:
1.展示它在 NP 中(问题的解可以在非确定性图灵机上以多项式时间验证); 2.展示一个已知为 NP-完全问题可以被“归约”为新问题。
那么我的问题是,第一个 NP-完全问题是如何被“证明”是 NP-完全的?曾经,已知的 NP-完全问题集合可能为零,这将使得无法使用上述过程中的步骤 2。
这让我想到是否存在另一种我不知道的证明方法。或者,由于缺乏已知的多项式时间解决方案,对于某些问题,整个 NP-完全属性可能被“假定”。(事实上,写下这篇翻译后,我不会感到惊讶,但我希望得到一些大师的反馈)。