作者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