未來數學家的挑戰【三、P 之外？】

三、P 之外？

本節之題目有點不平常，我們的目的是提醒讀者本文中常用之英文大寫的 P 是一個凡能用 O(nk) 計算量解決之問題之集合。而 P 之外加一個問號係指到目前為止，我們尚不知道 P 之外是否是一個空集合。

到目前為止，除了售貨員旅行問題之外，已經有上百有趣或有用的問題，無法用 O(nk) 的計算量來解決，我們在此列舉幾個例子。

問題1：售貨員旅行問題（甲）
即第一節所述之問題，不再重複，不過假定所有距離均為正整數 3 。

問題2：售貨員旅行問題（乙）
與第一題之條件相同，但現在有一個給定之正整數 B，問題是是否存在一條路徑其總距離不大於 B。（問題1與問題2在表面上相似，但在以後的理論上有很大的不同）

問題3：背袋問題（甲）
有物體 n 個，各重 w1,w2,…,wn，今欲將它們分為二袋，試問如何分法可使兩袋之重量最為接近。（不妨假定 wi 皆為正整數，這並未失去一般性。)

問題4：背袋問題（乙）
如上題，並給定一正整數 B，試問可否選出若干 wi，使其和

\begin{displaymath} S \leq \sum_{i=1}^{n} \frac{w_i}{2} \mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 47}} S \geq B \end{displaymath}

問題5：包裝問題
有 n 個各別重量小於 1 公斤的物品及足夠可以裝 1 公斤東西的盒子，今將物品裝於盒子之中，多個物品可裝於一盒，但任何一盒不得重於 1 公斤，試求最小的盒子數。

問題6：舞伴問題
今有 n 個男孩子與 n 個女孩子參加舞會，每個男孩與女孩均交給主持一個名單，寫上他（她）中意的舞伴（至少一人，但可以多於一人）。試問主持人在收到名單後，是否可以分成 n 對，使每人均得到他（她）所喜歡的舞伴。

問題7：庫存問題
某倉庫有 D 個存倉，排成一列，今有 n 批貨物，各可佔有一個或多個存倉，並已知各批物品存入與提出之日期。試問可否將各貨物存入庫裏不發生存倉不夠的困難且同一批貨物若需一個以上存倉時，其存倉必須相鄰。

問題8：
已知 a,b,n 三正整數，問是否存在一小於 n 位之正整數使得

\begin{displaymath} x^2 \equiv a \pmod{b} \end{displaymath}

問題9：

（甲） 給定一 n 位正整數 a，試問其是否為質數？
（乙） 給定一 n 位正整數 a，試問是否存在 m,n >1 且 a=mn？

問題10：分叢問題
已知空間 n 個點，並假定各點之間之距離為正整數，又給定兩正整數 K 與 B，問是否可將此 n 點分成小於 K 個不重合的子集，使得在同一子集內之任意二點距離均不大於 B？

現在可以看出這類問題的一般結構了。很顯然的，有些是極有用的問題，而有些可以轉換成有用的問題。例如舞伴問題，若把男孩與女孩換成工人與工頭，或醫生與病人就有大用了。這些問題到目前沒有一個可以證明是屬於 P 的，大家都猜測它們可能在 P 之外，即其計算量是呈指數增加的。

在60年代，已有些人把某些問題歸於一類了，即是幾個問題是互依的，若其中之一若屬於 P，則其他幾個也屬於 P，其證明方法大都是證明兩個互依問題中間有一個只需要用 O(nk) 時間來完成的橋樑。直到1971年古克 (Stephen A. Cook) 發表了〈The Complexity of Theorem Proving Procedures〉才把 P 之外約問題歸成了三大類，即 NP, NP-complete 及 NP-hard 4 ，現在談古克定律。