未來數學家的挑戰【七、結論+註釋】

七、結論

現在你明白二十世紀的大難題了，P=NP？用簡單的語言說，就是是否能找到一個只呈方次增加的方法去解決旅行、包裝、舞會等問題。平凡的問題，期待您不平凡的解答。

1. Gorey, M.R. and Johnson, D.S.《Computers and Intractability-A Guide to Theory of NP-Completeness》, 1979, Freeman and Company.

2. Pearl, J.《Hearistics-Intelligent Search Strategies for Computer Problem Solving》,1984, Addsion-Wesley.

3. Cook, S.A.〈The complexity of theorm-proving procedure〉, Proc. 3rd Ann. ACM Symp. on Theory of Computing, 1971, 151-158.

4. Jonhson, D.S. et. al.〈Worst case performance bounds for simple one-dimensional packing algorithms〉, SIAM J. Comp., 1974, 299-325.

5. Rosenkrantz, D.J. et. tl.〈An analysis of several heurishics for the traveling salesman problem〉, SIAM J. Comp., 1977, 563-581.

6. Sahin,S. and Gonzalez,〈P-complete approximation problems〉, J. ACM, 1976, 555-565.

7. Stockmeyer, L.J. and Meyer, P.R.〈Word problems requiring exponential time〉, Proc. 5th. Ann. ACM Symp. on Theory of Computing, 1973, 1-9.

8. Robertson,E. and Munro, I. 〈NP-completeness, puzzles, and games〉 Utilifas Math., 1978, 99-116.

註釋

...¹

排序 (Sorting) 的方法很多，但都不能低於 ，讀者可在一般 Database 的書中找到有關 Sorting 的法則。

...²

又稱呈多項式上升，但因一個 n 的多項式之大小，在 n 很大時都為第一項所支配，故可寫成 O(n^k)。

...³

並不失去一般性，即若距離不是正整數也可以把它們化成正整數。

...⁴

在古克的原文中，並沒有 NP-complete, NP-hard 之明確定義。但是由於他的論文，使這種分法顯得很自然。 不過 NP-hard 之定義仍因人而異，不一定同於本文。

...⁵

本文中之解決，均指一個 O(n^k) 計量算的解法。

...⁶

與情報人員之單線作用相同。一個諜報人員只知道他的頂頭上司及他的第一線下層下屬，其餘的人他都不知道。

...⁷

A,B,C 表任三城，而 d(A,B),d(B,C),d(C,A) 分別表示 A,B; B,C; C,A 城之距離，則 稱為三角不等式。

...⁸

指 19×19 之棋盤，許多計算機學家都是圍棋高手，中國的算盤與圍棋，好像包含了計算機的開始與終極。