上頁 1234567 次頁

未來數學家的挑戰
計算量問題
(第 3 頁)

楊照崑;楊重駿

 

首頁 | 搜尋

.原載於數學傳播十卷二期
.作者當時任教於美國佛羅里大學統計系;美國海軍研究實驗所

註釋
對外搜尋關鍵字
 
三、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 批貨物,各可佔有一個或多個存倉,並已知各批物品存入與提出之日期。試問可否將各貨物存入庫堣ㄤo生存倉不夠的困難且同一批貨物若需一個以上存倉時,其存倉必須相鄰。

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

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

問題9:
(甲) 給定一 n 位正整數 a,試問其是否為質數?
(乙) 給定一 n 位正整數 a,試問是否存在 m,n >1a=mn

問題10:分叢問題
已知空間 n 個點,並假定各點之間之距離為正整數,又給定兩正整數 KB, 問是否可將此 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 ,現在談古克定律。

   

上頁 1234567 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:王昱昇 / 校對:陳文是 / 繪圖:簡立欣 最後修改日期:6/29/2002