※ 引述《mqazz1 (无法显示)》之铭言： : 我在看NP-complete的时候 : 讲义上说凡是NP-complete领域所讨论的problem一定是以decision形式出现 : 然後他有问一个问题 : sorting problem: 将a1, a2, ..., an由小排到大 : 请问这种问题要怎麽把它转成decision的形式? : 谢谢 这题有不同可能的答案. (最近家教才教到, 提供一些想法!) 当然最直接的 "给定 input A[1..n], 请问是否 A[1] <= ... <= A[n]?" 是一个可能. 我觉得底下这个方法比较有趣: 考虑问题 SORT', 给定 input A[1..n], 求一 A 的重排 B[1..n] 使得 |A[n] - A[n-1]| + |A[n-1] - A[n-2]| + ... + |A[2] - A[1]| 最小. 不难证明 SORT' 跟 SORT 等价. 这个问题可以很轻易改成 decision 形式: 考虑问题 SORT(D), 给定 input A[1..n] 与常数 c, 是否存在 A 的重排 B[1..n] 使得 |A[n] - A[n-1]| + |A[n-1] - A[n-2]| + ... + |A[2] - A[1]| <= c ? 很类似 TSP 改成 TSP(D) 的方式! -- Chicken's Finite Playground http://finiteplayground.wordpress.com/ Algorithms, Computational Complexity, Graph Theory, and Anything... FINITE!! --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 220.135.37.158