np-complete

4热度

2回答

“证明它是NP完全的以确定给定的输入G和k是否G既有k大小集合又有大小为k的独立集合请注意，这是1个问题，而不是2;答案是肯定的当且仅当 G有这两个子集。“ 在我的算法课程中，我们遇到了这个问题，一大群学生无法弄清楚。这是我们迄今为止的... 我们知道集团和独立集合问题都是NP-Complete。我们也知道，NP中给出了一些“证书”，这个问题的验证。这个问题在某种程度上减少了上述问题（它包含独立

6热度

4回答

这个问题是否完整？

假设有一行x装满饰品（随机数量）的箱子，在明显（你可以看到每个箱子里有多少饰品）。现在有两名球员可以轮到他们从任何一端选择一个垃圾桶。他们不能放弃回合。提出一个玩家获得最大数量小饰品的策略。 x是偶数。这是一个NP完整的问题？它是否类似于布尔SAT？

0热度

1回答

费用分配问题

我有一个问题，我坚持，并且无法找到任何地方开始，所以我无望转向了计算器。该问题希望我们找出它是np-hard还是多项式，如果它的np-hard证明了np-completeness，则给出算法。问题如下：产品存在n个模块。有两家公司可以构建每个模块，但有一些成本（c_ij，i：模块编号，j：公司编号）。如果模块a和b由不同的公司构建，他们也有额外的成本，（p_ab）。模块a和b不必是连续的，相

2热度

1回答

这是最佳时间表任务NPC吗？

我自愿编写一个计划安排家长会议。校长希望家长选择3种可能的日期时间来访问他们的英语和数学老师（同时）。一旦所有的父母选择了3个日期时间，我应该找出安排家长教师会议的最佳方式，以便最大数量的家长能够与两位教师见面。（如果有时间冲突，数学老师不能参加本次会议，家长只会用英语老师见面）我不知道很多关于NP型问题，但是当我听到“最佳”和“时间表”在一起，我开始怀疑...... 我已经告诉校长我不能那

3热度

2回答

寻找一个模型来表示这个问题，我怀疑可能是NP完全

（我已经改变了这个问题的细节，避免NDA的问题。我知道，如果采取从字面上看，有到更好的方法运行这个理论公司）在A公司生产的1000种产品中，有一组仓库，每个仓库都能够存储和分配200种不同的产品。每个仓库都备有200种产品和分配的订单，然后他们可以从库存中进行填充。的挑战是，每个仓库必须自给自足。将有一个任意数量的产品（通常为5-10个）的订单，分配给仓库。然后仓库为订单打包所需产品，并将它们

0热度

2回答

算法来检查给定的图是否是另一个图的子图

我假设我们有2个带标记的图G和T，并且该算法确定G的子图是否与主图T和子图G中的对应顶点应该有相同的标签

5热度

5回答

这个组合优化问题NP-hard？

我工作的组合优化问题，我怀疑是NP难，遗传算法一直与我们的数据集一直工作。我们是一个研究小组，并计划在我们的领域发布我们的研究成果（而不是数学或CS），并且我希望在发送手稿供审阅之前探索NP难题。主要有两个问题： 1）我想知道这个特别的优化问题，是否进行了研究。我已经严重搜查了点燃，但没有看到任何完全相同的东西。 2）如果这个问题没有被研究过，我可能会在做一个可证明性证明的时候做出一些尝试，并且

3热度

1回答

证明NP完全问题

的我们给出集合A = {A 1 ，一个，...，一个Ñ} 给定一个名为B的子集，B ，...，B m。如果一个名为H的子集与所有给定的B相交，我们称之为“覆盖子集”。对于给定的A和Bs，有大小为K的任何“覆盖子集”（H的基数是K）吗？证明这个问题是NP-Complete。我们应该将一些已知问题减少为“覆盖子集”问题。

6热度

3回答

如何判断贪婪算法是否足以找到最小硬币更改？

minimum coin change problem是一个NP完全问题，但对于某些硬币组，贪婪算法（首先选择最大面额）起作用。给定一组表示硬币值的整数，确定贪婪算法是否足够的最快算法是什么？一个显而易见的方法是建立你的动态规划解决方案，直到最大的面额，并看看它是否产生比贪婪的方式更好的解决方案。但是有没有更快的“数学方法”来检测它？

0热度

1回答

这个数据共享问题是NP问题吗？

这是我的问题： P2P网络中有n个对等点，它们请求相同的数据块;并有一些限制。 1.具有自己的上传带宽的对等者，平均带宽是数据块的大小。 2.同行对这个数据块有不同的截止日期。如果一个对等方在截止日期之前没有获得整个块，那么它必须搜索服务器帮助。 3.对等体只能传输整个数据块的数据（部分或全部）。目标是尽量减少服务器总的上传，我不能弄明白，如果它有一个最佳算法或它是一个NP问题。截止时间先行或最