[理工] 演算法 NP只包含decision problem？

看板Grad-ProbAsk作者 (GAPiNAS)時間10年前 (2016/01/10 16:33), 編輯推噓8(8推 0噓 17→)
留言25則, 3人參與, 最新討論串1/1
由於不確定答案，想請板上高手幫忙解決 NP只包含decision problem？ 我認為是True，因為optimization problem無法在polynomial time 驗證？ 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.97.135 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452414822.A.000.html
推
01/10 16:36, , 1F
前幾天朋友po給我的 可以參考看看http://lm.facebook
01/10 16:36, 1F
→
01/10 16:36, , 2F
.com/l.php?u=http%3A%2F%2Fbluelove1968.pixnet.net
01/10 16:36, 2F
→
01/10 16:36, , 3F
%2Fblog%2Fpost%2F222283186-%25E8%25AB%2596p%2Cnp%
01/10 16:36, 3F
→
01/10 16:36, , 4F
2Cnp-hard%2Cnp-complete%25E5%2595%258F%25E9%25A1%
01/10 16:36, 4F
→
01/10 16:36, , 5F
258C&h=PAQFQkQt2&s=1
01/10 16:36, 5F
→
01/10 16:39, , 6F
好長...天啊
01/10 16:39, 6F
推
01/10 18:59, , 7F
其實這只是定義的問題 一般的定義都是只討論 decision
01/10 18:59, 7F
→
01/10 18:59, , 8F
problem
01/10 18:59, 8F
推
01/11 08:54, , 9F
我記得老師上課時說過這兩個問題大多能互相轉換
01/11 08:54, 9F
→
01/11 08:54, , 10F
比如你要求某個圖的longest path 這是opt. 問題
01/11 08:54, 10F
→
01/11 08:55, , 11F
但你也可以去驗證它存不存在長度為三的longest path
01/11 08:55, 11F
→
01/11 08:56, , 12F
找不到就再驗證是否有長度四的 以此類推
01/11 08:56, 12F
→
01/11 08:56, , 13F
這樣就把opt.問題轉成decision問題了
01/11 08:56, 13F
→
01/11 08:57, , 14F
以上是憑印象回答的 有錯誤再麻煩指正
01/11 08:57, 14F
推
01/11 09:03, , 15F
irenelove: 你如果用 TSP 問題想 就會發現這種轉換有問題
01/11 09:03, 15F
→
01/11 09:04, , 16F
假設邊的權重都是整數 你會需要用指數個 decision 問題
01/11 09:04, 16F
→
01/11 09:04, , 17F
來驗證 所以這種轉換方法是沒意義的 要使用二分法..
01/11 09:04, 17F
推
01/11 15:19, , 18F
不好意思我資質駑鈍 請問為什麼邊權重是整數會需要指
01/11 15:19, 18F
→
01/11 15:19, , 19F
Decision problem呀><
01/11 15:19, 19F
→
01/11 15:19, , 20F
*指數個
01/11 15:19, 20F
推
01/11 15:21, , 21F
不能比如所有邊權重和是n 我去驗證是否含長度x的TSP x
01/11 15:21, 21F
→
01/11 15:22, , 22F
從1到n這樣子嗎
01/11 15:22, 22F
推
01/11 20:40, , 23F
是的 但是所有權重和 n 你在輸入只需要 O(lg n) bits 表示
01/11 20:40, 23F
→
01/11 20:40, , 24F
所以你等於是要花指數時間來驗證..
01/11 20:40, 24F
推
01/11 23:05, , 25F
噢！了解了 謝謝F大
01/11 23:05, 25F
‣ 更多 GAPINAS 的文章
文章代碼(AID): #1MaXTc00 (Grad-ProbAsk)