交大資演 NP問題

[周宗鴻]

Assume P != NP

For each of the following problems, decide whether it is a P-problem or an

NP-hard (or NP-Complete) problem, or neither.

(1) Find a shortest simple path between two nodes in a directed graph with

negative and/or postive edge weights, and containing negative weight cycles.

老師妳好，這題在題庫班答案給 neither，但是最近在複習的時覺得有點奇怪想問一下

題庫班好像說是因為「負 cylce 會讓這個問題變得沒有意義」，但是題目有說是simple path

但 path 本身的定義不就是不包含重複點嗎？那這樣不是應該是屬於P嗎？還是有哪個環節我漏考慮了，再麻煩老師了 

[林立宇]

拍謝我解題時漏看了 "simple" path

那這個問題其實會是個 NP-hard 的問題

因為 longest path problem 可以 reduce 到這個問題的 decision 版本:

在限制 instance graph 含有正 cycle 的情形下, 

longest path problem 仍為 NP-complete

所以將 LP 問題之 problem instance G 中所有邊的 weight 皆取負

則可成為此問題的一個 problem instance G'

這樣找到 G' 的 shortest simple path 就相當於找到 G 的 longest simple path

謝謝同學幫忙更正

[周宗鴻]

了解了，謝謝老師

[莊家豐]

老師您好，想請問那這個問題是NP-Complete嗎？因為妳只有回答是NP-Hard@@?

然後想請問simple path和path的定義有差別嗎？
不是都指不經過重複的點？

最後想請問我們之前所學的shortest path 演算法(Dijkstra, Bellman-Ford ,Floyd-warshall)，皆不允許負cycle的存在。

是因為負cycle會使得這些演算法解不出來嗎？
還是是因為會讓整個問題沒有意義？

因為我想到的是，如果以path的定義(即不經過重複的點)，這樣圖中s→a→t 算不算是s至t的shortest path？

若是的話，不就存在shortest path?(不經過重複點的最短路徑) 只是它並不為最短之走法

[林立宇]

1. 若問題是 decision version 我們才可以說它是 NP-complete
我會說 NP-hard 是因為題目描述的是一個 optimization problem
不是 decision version
如果是 decision version 就是 NP-complete

2. path 其實沒有規定要不經過重複點
只是在題目未特別說明的情形下通常指的會是 simple path

3. 主要還是因為 negative cycle 會使得問題變得無意義
因為 shortest path 不 well-defined
在 shortest path problem 中, path 不需要是 simple path
所以你說的 s→a→t 那不是我們一般講的 shortest path
因為在你畫的這張圖上有負 cycle, 無法討論 SP
我們前面的討論就是在說, 如果問題換成是在這個圖上請你找出 s→a→t 這種 path
那這個問題就是 NP-hard 的問題

[莊家豐]

突然領悟了好多東西呀！太感謝老師了T.T