如何证明一个概率是np完整的并且在np中？

Question

鉴于部门需要一个委员会来选择部门负责人。委员会不能包括有利益冲突的人。输入包括：

• 所需的委员会人数
• 所有人列表
• 所有有冲突的人的清单。

目标是确定是否有这样规模的无冲突委员会。

如何显示此问题是NP完全的并且在NP中？

Answer 1

由于这是99.99％的家庭作业，所以我只给您一个简短的“答案”：

尝试减少Indepedent Set Decision Problem解决您的问题。

还有一个有用的注释是，如果您证明问题是NPC，那么它是NP

Answer 2

显示问题是NP完全要求，以证明它是NP中的。

1. 熟悉NP完整问题的子集
2. 证明NP硬度：将NP完整问题的任意实例简化为您的问题的实例。这是最大的一块蛋糕，而对NP Complete问题的熟悉也值得付出。根据您选择的NP完整问题，减少难度将或多或少地变得困难。
3. 证明您的问题出在NP上：设计一种算法，该算法可以在多项式时间内验证实例是否为解。

显示它在NP中：

给出一个随机的子集N，您如何检查他们是否组建无冲突委员会？

应该足够容易。算法不必在内存或大小上高效，只需正确即可。在子集中形成所有可能的对，并检查对是否在冲突匹配列表中。

熟悉NP完整性：存在一些特定的NP完全问题，这些问题在提高NP硬度方面非常受欢迎。例如Karp's 21 NP-complete problems

证明：通过快速分析您的问题，我可能最初会尝试使用Vertex Cover NP完整问题，尤其是由于conflict子句。鉴于您对委员会大小有所限制，也许您可​​以先尝试最小顶点覆盖。

祝你好运。>>

Answer 3

NP证明通常与已知的NP问题等效。例如，参见Karp的21个NP完全问题。 SAT是最常用的一种（也请参阅Cook-Levin定理）。您可以尝试使用少量人员来创建逻辑门，其中一个人成为委员会成员取决于另外两个人的成员身份。例如，这就是NP证明如何在Conway的《人生游戏》和Morpion纸牌等游戏中发挥作用。

Answer 4

要证明问题是np完全的，您首先必须证明问题出在np中。您可以这样做以形成证书，因此您将选择一个委员会规模，一个人员列表，有利益冲突的人员列表以及一个委员会。然后，如果您可以验证（而不是证明）委员会在多项式时间内是否有效，则问题出在np。