[理工] 演算法 flow、NP

看板Grad-ProbAsk作者sdfg014025xx (隨便就好)時間7年前 (2019/01/23 13:48)推噓3(3推 0噓 4→)

留言7則, 1人參與討論串1/1

我前面一些敘述沒拍，這題是說有C個class和R個classroom然後要分配教室，每個課都要有獨立的一間教室用flow network的解法 a的轉換我能夠了解，我想問的是b小題的證明，請問為什麼這樣就能證明了？兩個方向的都有點不太懂，希望有高手能再提點一下 2. https://i.imgur.com/tZVPezp.jpg

上面中央那題我不太明白為什麼這樣就能驗證了，應該說不太懂為什麼這樣子寫就可以了，是因為題目這要要求嗎？要怎麼找一組S包含於A去驗證？下面成大那題我想要問跟np的比較如果選項是說Let X be an Np-hard problem.If a problem Y can polynomials reduce to X,then Y is Np-hard，這樣的選項是錯的因為方向錯了，但在這題這樣子就是成立的？是因為他有先說P1可以 polyReduce到P2已經成立，所以後續這樣講是對的，還是因為這只是p的關係？問題有點多，感謝各位 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.114.144 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548222495.A.6DD.html

推

ekids1234

01/25 23:00, 7年前 , 1^F

01/25 23:00, 1^F

→

ekids1234

01/25 23:00, 7年前 , 2^F

01/25 23:00, 2^F

推

ekids1234

01/25 23:05, 7年前 , 3^F

01/25 23:05, 3^F