推 qoojordon: 謝謝F大的回答 10/20 19:43
※ 引述《qoojordon (穎川琦)》之銘言：
: 這邊有3個演算法的觀念想請教各位板友
: Q1: NP-C的證明方式 與 reduce的概念
: 在探討一個問題 B 是不是NP-C的時候 , 都會用reduce的手法去說明 B 比較難
: 以我目前的理解 , 把問題A reduce 到問題 B , 代表 B 比 A 難
: 我的理由: 如果要知道B是否有解,可以用符合問題A的instance,經過多項式時間內
: 的f轉換,得到問題B的解
: 以證明Longest Path是NP-C為例 :
: 已知難度為NP-C的 問題A : G是否有Hamilton path ?
: 欲證明難度為NP-C的問題B : G是否存在一simple path長度≧k
: 要證明問題B為NP-C須說明兩件事情
: (1) 問題B 是 NP
: (2) 問題B 是 NP-C (用已知的NP-C問題reduce到問題B)
: 我的問題 : 證明(2)是否只要說明 A→B 即可 ?
: 書本上看到的寫法都會證明兩邊 A <--> B , 不太能理解為什麼需要證明"必要條件"(
: 往左的箭頭A←B) , 如果要說明問題B比問題A難,不是只要將NP-C難度的問題A reduce
: 到問題B就可以說明了嗎 ?
你有點混淆了，在(2)中，你是要證明A可以reduce到B。
但是在證明可以reduce的過程中，你必須要創造一個多項式時間的reduction。
使得
對於任何 A 的一個 instace 答案是 yes
若且唯若 reduce 到 B 的 instance 答案是 yes
在證明 if and only if 的地方，你會需要證明兩邊，但是reduce本身只有單邊。
只證明單邊是不對的，如果你把reduce的定義改成只要證明單邊。
反例是如果問題 C 是一個 trivial 問題，答案永遠yes。
那所有問題的 yes instance 當然都可以reduce到 C 上。
: ----------------------------------------------------------------------------
: Q2: 0-1 knapsack為NP的複雜度論述
: 書本上說明0-1背包問題的複雜度為 nW , 更確切的表示為 n2^(logW) , 因此
: 並不是一個多項式時間服雜度的問題 , 有點不懂黃色那個轉換的來由?
W 是輸入的數值，但是要表示 W 只需要 log W 位元。
以時間複雜度的角度來看，輸入log W位元，但是執行時間是W情況，
跟輸入是長度是 n 位元，執行時間是 2^n 是一樣的，都不是多項式時間。
: ----------------------------------------------------------------------------
: Q3: Minimum Spanning Tree(MST) & Flow Network
: Q3-1(T or F) 如果一圖G的edge weight皆不相同 , 則G的MST唯一
: Q3-2(T or F) 如果一個flow network的每個edge之capacity皆不相同 ,
: 則maximum flow唯一
: 上述兩題是我自己想到的狀況 , 想和各位板友確認
: 我自己覺得是 F , T
: 理由3-1: 假設有五根edge , weight分別為1~5 , MST包含的edge可以是
: {1,5,3}或{2,3,4} , 所以應該不唯一 , 只是有點不嚴謹 , 不
: 曉得是否正確?
http://en.wikipedia.org/wiki/Minimum_spanning_tree#Uniqueness
: 理由3-2: 可能存在數個由不同組edge組成的 min Cut , 但都對應到相同的max flow值,
: 是用類似3-1的情況想像的 , 不曉得是否正確? (附帶一問 , 這種說法應該
: 只能確保流到t的最大量,但不能確認中間的路徑走的是相同的吧?頂多保證在
: cut1和cut2的edge必定flow=capacity )
考慮小的 Series-parallel graph，應該可以找到反例吧..
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.148
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1413720502.A.DD0.html
※ 編輯: FRAXIS (129.170.195.148), 10/19/2014 20:16:22