作者mqazz1 (无法显示)
站内Prob_Solve
标题[问题] sorting problem转decision problem
时间Fri Sep 9 20:26:33 2011
我在看NP-complete的时候
讲义上说凡是NP-complete领域所讨论的problem一定是以decision形式出现
然後他有问一个问题
sorting problem: 将a1, a2, ..., an由小排到大
请问这种问题要怎麽把它转成decision的形式?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.166.118.226
1F：推 shaopin:sorting的decision就是两两比较的时候所作的comparison 09/09 23:13
2F：推 LPH66:不对吧...那样会变成"问某序列是不是已排序" 09/10 00:41
3F：→ LPH66:这和 sorting problem 是差很多的... 09/10 00:41
4F：→ chunhsiang:我是不太懂...但会不会是指CNF那个? 09/10 02:30
5F：→ chunhsiang:另外sorting problem的化简好像是找最大问题 09/10 02:34
7F：→ DJWS:看起来如同一楼所说 09/10 07:50
8F：推 LPH66:楼上似乎看漏了 他是说字串排序是 NP-easy 09/10 13:20
9F：→ LPH66:这和 sorting 的 decision problem 版根本没有关系... 09/10 13:20