作者sdfg014025xx (随便就好)
看板Grad-ProbAsk
标题[理工] 演算法 flow、NP
时间Wed Jan 23 13:48:12 2019
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548222495.A.6DD.html
1F：推 ekids1234: 第二个问题的 : 他要求 nondeterministic，所以用"猜" 01/25 23:00
2F：→ ekids1234: 的就好，然後再去验证 01/25 23:00
3F：推 ekids1234: 然後成大那个，P2 是 P，P1 又比 P2简单，直觉 P1 是 P 01/25 23:05
4F：→ ekids1234: 但...Y re 到 X(NP-Hard)，若 Y是 NP Hard -> 合理 01/25 23:07
5F：→ ekids1234: 但也可能 Y 不是 NP-Hard (但我举不出例子 Orz ) 01/25 23:07
6F：推 ekids1234: 不对，如果 Y 不是 NP 的话 P 可 re 到 X means P=NP耶 01/25 23:09
7F：→ ekids1234: Let X be ... 那段有出成题目吗 ? 01/25 23:11