如何证明一个问题是NP完全问题？

Question

我有一个调度问题需要解决。我需要证明该问题是NP完全问题。有什么方法可以证明它是NP完全问题吗？

- thetna

---

阅读卡普的《组合问题中的可约性》。 - Paul Hankin

Answer 1

展示一个问题是NP完全的，你需要：

展示它属于NP

换句话说，给定一些信息C，您可以创建一个多项式时间的算法V，该算法将为每个可能的输入X验证X是否在您的域中。

举例

证明“顶点覆盖问题”（即对于某些图G，是否存在一个大小为k的顶点覆盖集，使得G中的每条边都至少有一个顶点在覆盖集中？）属于NP：

• 我们的输入X是一些图G和一些数字k（这是从问题定义中得出的）。

• 取C为“图G中大小为k的任何可能的顶点子集”。

• 然后，我们可以编写一个算法V，在给定G、k和C的情况下，在多项式时间内返回该顶点集是否为G的顶点覆盖。

然后，对于每个图G，如果存在某个“可能的大小为k的G中的顶点子集”是一个顶点覆盖，则G属于NP。 注意，我们不需要在多项式时间内找到C。如果我们可以这样做，该问题将属于

。

注意算法V应该针对每一个G，对于某些C都能工作。对于每个输入，应该存在信息可以帮助我们验证输入是否在问题域内，也就是说，不应该存在信息不存在的输入。

证明它是NP难题

这涉及到获取一个已知的NP完全问题，比如SAT，其中包括形式为：

(A或B或C)和(D或E或F)等布尔表达式的集合……

其中表达式是可满足的，也就是说存在一些布尔值的设置，使得表达式成为真。

然后将NP完全问题在多项式时间内约化到你的问题上。

也就是说，给定一些输入X用于SAT（或者你正在使用的任何NP完全问题），创建一些输入Y用于你的问题，使得当且仅当X在SAT中时，Y在你的问题中。函数f：X→Y必须在多项式时间内运行。

在上面的例子中，输入Y将是图形G和顶点覆盖的大小k。

对于一个完整的证明，你需要证明以下两点：

• X在SAT中=>Y在你的问题中

• Y在你的问题中=>X在SAT中。

marcog的答案中包含了一个链接，链接中提到了其他几个可以通过约化转化为你所面临问题的NP完全问题。

脚注：在第二步（证明它是NP难问题）中，只要将另一个NP难问题（不一定是NP完全问题）约化到当前问题上就可以了，因为NP完全问题是NP难问题的子集（且也属于NP）。

- Laila Agaev

---

我想知道这背后是否存在缺失的数据或循环推理。我的意思是，在不将问题“参照已经在NP中的其他问题”的情况下，如何“证明”一个问题属于NP？这就像说“它是由铁制成的，因为它的部分已知是铁制的”，这不是一个完全的证明。 - Hernán Eche

据我所记，有一个名为库克-莱文定理的定理，它指出SAT问题是NP完全问题。该证明比我上面概述的要复杂得多，我不认为我可以用自己的话解释清楚它。 - Laila Agaev

更准确地说，Cook-Levin定理表明SAT是NP完全问题：任何处于NP问题集合中的问题都可以在多项式时间内通过一个确定性图灵机被归约到判断一个布尔公式是否可满足（SAT）的问题上。这就是你所询问的缺失部分。如果您在维基百科上查找该定理，将会有证明，并且您可以在证明中引用该定理。尽管如此，将SAT归约到给定问题是我所学证明NP完全性的方法。 - Laila Agaev

所以我的问题最终是，如果SAT问题可以在多项式时间内解决，即P = NP问题。谢谢你的回答。 - Hernán Eche

请问为什么我们不能在第二步将 NP-hard 问题简化到我们想要解决的问题呢？这是否必须是一个 NP-complete 问题？ - MLT

@MLT 你绝对可以将一个NP-hard问题简化为你想要证明的问题。你可以查看这个笔记（第6页），希望能有所帮助。http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/30-nphard.pdf - zs2020

Answer 2

你需要将一个NP完全问题转化为你所面临的问题。如果这个转化能够在多项式时间内完成，那么你就证明了你所面临的问题是NP完全问题。因为问题本身已经属于NP问题，所以它不会比NP完全问题更简单，因为它可以在多项式时间内被规约成NP完全问题，从而使得它成为NP难问题。

请参见 http://www.ics.uci.edu/~eppstein/161/960312.html 的结尾了解更多信息。

- moinudin

---

认同那些能够用易懂的语言解释问题的人，而非仅是给出一堆我几乎不理解的关键字。+1 - ColacX

第一句话前后颠倒了：你需要将已知的NP完全问题归约到你自己的问题。这表明你的问题至少和已知的NP完全问题一样难。第（b）部分也是不正确的：如果你已经找到了归约，那么你已经知道你的问题是NP难的；唯一的问题是它是否在NP中（有些问题，如停机问题，不在NP中）。当且仅当它是NP难的并且在NP中时，它才是NP完全的（即“NP完全”比“NP难”更具体）。 - j_random_hacker

我不会说a)会导致矛盾，因为我们不知道P是否等于NP。 - chtenb

Answer 3

为了证明一个问题L是NP完全问题，我们需要完成以下步骤：

1. 证明你的问题L属于NP（也就是证明在多项式时间内可以验证给定解）
2. 选择一个已知的NP完全问题L'
3. 描述一个算法f将问题L'转化为问题L
4. 证明你的算法是正确的（形式上，如果且仅当x∈L'时f(x)∈L）
5. 证明算法f在多项式时间内运行

- Albert s

Answer 4

首先，您需要证明该问题至少属于NP。

然后，您需要找到另一个已知为NP完全的问题，并展示如何将NP难问题多项式归约为您的问题。

- cadolphs

---

不行。你需要展示如何从一个NP完全问题规约到你的NP问题，以证明它是NP完全问题，并且必须证明它属于NP问题集合。除非你无法证明它属于NP问题集合，否则NP难度并不涉及其中。 - mrmemio29

Answer 5

1. 熟悉 NP 完全问题的子集
2. 证明 NP 难度：将任意一个 NP 完全问题实例化为你的问题实例。这是最重要的部分，需要对 NP 完全问题非常熟悉。根据所选的 NP 完全问题不同，约简过程可能会更加困难。
3. 证明你的问题属于 NP：设计一种算法，可以在多项式时间内验证一个实例是否是解决方案。

- UmNyobe