功能性問題

维基百科,自由的百科全书
跳转至: 导航搜索

計算複雜性理論內,功能性問題或者函式問題(function problem)是一種計算問題(en:computational problem),我們對任何一種輸入都預期會有單一個輸出,但是輸出不像是決定性問題一樣這麼單純。換句話說,輸出不只YES 跟 NO。重要的範例像是旅行推銷員問題,詢問一張圖是否有可以繞過每一點的不重複路徑(輸出為路徑),以及整數分解,輸出為輸入的質因數。

因為沒有明顯類比的語言,功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多,在解決輸入輸出之間的轉換,功能性問題歸約的過程也比較微妙。 功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機多項式時間裡面可以解決的功能性問題(類似於決定性問題的P),而FNP是指可以用非確定型圖靈機多項式時間裡面可以解決的功能性問題(類似於決定性問題的NP)

對所有能在多項式時間內解決的的功能性問題,一定存在一個雷同的決定型問題,可以用多項式時間圖靈歸約將後者歸約為前者的方式,解決這個功能性問題。舉例,旅行推銷員問題的決定型問題版本如下:

給定一個有權重的有向圖和一個整數K,是否存在一個哈密頓路徑 (或者哈密頓回路,如果問題指定推銷員在經過所有城市後一定要回到家)並且走過的路徑權重相加小於或者等於K?

給定這個決定性問題的解答,我們則可以解決旅行推銷員問題如下:

n為邊的數量,w_i則是邊i的權重。首先我們重新設定邊的權重,給予每個邊i新的權重w'_i = 2^{(n+1)} w_i + 2^i。 這並不會改變最短路徑本身,但是會保證這路徑是唯一的。然後,將所有的邊權重加起來,得到這個圖的總權重M。接著,我們使用折半搜索算法找出這條最短路徑的權重: 是否有權重輕於< M/2的路徑?;是否有權重輕於< M/4的路徑?…等等。找到最短路徑的權重W之後,我們藉由以下演算法確定特定某個邊i是否在這個路徑上:修改i的權重為W+1之後,詢問這個圖是否還是有一個權重為W的哈密頓路徑?如果修改後的圖裡面不存在這條路徑, 則i這個邊必定在原圖的最短路徑裡面,反之,如果修改後此路徑還是存在,則i不在原來的路徑之內。

這個演算法將旅行推銷員問題的時間複雜度放進FPNP內 (可以在多項式時間之內,以決定性圖靈機和一個能解決NP問題的神諭解決的問題),並且事實上是這個複雜度類的完備問題。


參考資料[编辑]

  • Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, ISBN 155860474X, p. 45-51
  • Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0132288060, section 28.10 "The problem classes FP and FNP", pp. 689-694

相關條目[编辑]

最佳化問題