简单减少（NP完整性）

我正在寻找一种方法来证明bicriteria最短路径问题已完成。即，给定与长度和重量的曲线图，我需要知道如果存在在从s曲线图中的路径到t与总长度< = L和重量< = W.简单减少（NP完整性）

我知道我必须采取NP完整的问题，并减少到这一个。我们可以选择以下问题：3-SAT，独立集，顶点覆盖，哈密尔顿循环和三维匹配。

任何想法可能是可行的？

谢谢

2009-11-20 Allen

你可能想要停下教授的办公时间。 1-1时间与计算机科学phds是你的教育宝贵的一部分。你应该尽可能地利用它。 – 2009-11-20 02:45:50

不幸的是，我在这里没有我的Garey和Johnson的副本，也不记得其中的一些问题。如果您要编辑问题以提供快速定义，可能会帮助人们找到它们。（例如：3-SAT：给定一组布尔变量，以及一组将OR变量放在一起的三个变量，其中一些可能被否定，您能否将真值分配给变量，以使所有的子句都成立？） – 2009-11-25 15:23:31

你试过谷歌吗？第三命中：

http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_416/_article

这篇文章是付费观看，但谷歌的缓存提供前期最重要的一点：

“不幸的是，多目标的情况下（包括bicriteria情况下）为NP 。-complete（3）

和参考点：

（3）M. Garey和D.约翰逊：计算机和顽固性：指南NP-完整性，纽约的理论：弗里曼（1979）

这是此表格问题的标准参考。

所以......你看过Garey和Johnson吗？我没有副本在这里检查，但是当我做了比赛时，这是我的目标。

来源

2009-11-25 15:14:46 Eric

事情是，Garey和约翰逊真正有用的是NP完全问题的大量汇编。通常你的问题会在那里（我假设教授会检查这个），否则这是一个很大的问题来源，试图减少到你得到的。在这种情况下，学生有五个问题可供选择，这比G＆J中的数百个（字面上）处理起来要容易得多。 – 2009-11-25 15:19:36

有时，G＆J将通过暗示推导链来帮助解决这样的问题......要么直接涉及一个更为熟悉的问题，要么通过一些中间问题来提出构建直接证明的策略。 – Eric 2009-11-25 15:55:40

简单减少（NP完整性）

回答

相关问题