[問題] sorting problem轉decision problem

[mqazz1 (無法顯示)]

我在看NP-complete的時候

講義上說凡是NP-complete領域所討論的problem一定是以decision形式出現

然後他有問一個問題

sorting problem: 將a1, a2, ..., an由小排到大

請問這種問題要怎麼把它轉成decision的形式?


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.166.118.226
推 shaopin:sorting的decision就是兩兩比較的時候所作的comparison
推 LPH66:不對吧...那樣會變成"問某序列是不是已排序"
→ LPH66:這和 sorting problem 是差很多的...
→ chunhsiang:我是不太懂...但會不會是指CNF那個?
→ chunhsiang:另外sorting problem的化簡好像是找最大問題
推 DJWS:http://en.wikipedia.org/wiki/NP-easy
→ DJWS:看起來如同一樓所說
推 LPH66:樓上似乎看漏了  他是說字串排序是 NP-easy
→ LPH66:這和 sorting 的 decision problem 版根本沒有關係...