→ ken52011219: .com/l.php?u=http%3A%2F%2Fbluelove1968.pixnet.net 01/10 16:36
→ ken52011219: %2Fblog%2Fpost%2F222283186-%25E8%25AB%2596p%2Cnp% 01/10 16:36
→ ken52011219: 2Cnp-hard%2Cnp-complete%25E5%2595%258F%25E9%25A1% 01/10 16:36
→ ken52011219: 258C&h=PAQFQkQt2&s=1 01/10 16:36
→ ken52011219: 好長...天啊 01/10 16:39
推 FRAXIS: 其實這只是定義的問題 一般的定義都是只討論 decision 01/10 18:59
→ FRAXIS: problem 01/10 18:59
推 irenelove: 我記得老師上課時說過這兩個問題大多能互相轉換 01/11 08:54
→ irenelove: 比如你要求某個圖的longest path 這是opt. 問題 01/11 08:54
→ irenelove: 但你也可以去驗證它存不存在長度為三的longest path 01/11 08:55
→ irenelove: 找不到就再驗證是否有長度四的 以此類推 01/11 08:56
→ irenelove: 這樣就把opt.問題轉成decision問題了 01/11 08:56
→ irenelove: 以上是憑印象回答的 有錯誤再麻煩指正 01/11 08:57
推 FRAXIS: irenelove: 你如果用 TSP 問題想 就會發現這種轉換有問題 01/11 09:03
→ FRAXIS: 假設邊的權重都是整數 你會需要用指數個 decision 問題 01/11 09:04
→ FRAXIS: 來驗證 所以這種轉換方法是沒意義的 要使用二分法.. 01/11 09:04
推 irenelove: 不好意思我資質駑鈍 請問為什麼邊權重是整數會需要指 01/11 15:19
→ irenelove: Decision problem呀>< 01/11 15:19
→ irenelove: *指數個 01/11 15:19
推 irenelove: 不能比如所有邊權重和是n 我去驗證是否含長度x的TSP x 01/11 15:21
→ irenelove: 從1到n這樣子嗎 01/11 15:22
推 FRAXIS: 是的 但是所有權重和 n 你在輸入只需要 O(lg n) bits 表示 01/11 20:40
→ FRAXIS: 所以你等於是要花指數時間來驗證.. 01/11 20:40
推 irenelove: 噢！了解了 謝謝F大 01/11 23:05