[理工] 演算法 flow、NP

[sdfg014025xx (隨便就好)]

1.
https://i.imgur.com/SpgdUFX.jpg
我前面一些敘述沒拍，這題是說有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: 第二個問題的 : 他要求 nondeterministic，所以用"猜"
→ ekids1234: 的就好，然後再去驗證
推 ekids1234: 然後成大那個，P2 是 P，P1 又比 P2簡單，直覺 P1 是 P
→ ekids1234: 但...Y re 到 X(NP-Hard)，若 Y是 NP Hard -> 合理
→ ekids1234: 但也可能 Y 不是 NP-Hard (但我舉不出例子 Orz )
推 ekids1234: 不對，如果 Y 不是 NP 的話 P 可 re 到 X means P=NP耶
→ ekids1234: Let X be ... 那段有出成題目嗎 ?