函數問題

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

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

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

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

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

為邊的數量,則是邊的權重。首先我們重新設定邊的權重,給予每個邊新的權重。這並不會改變最短路徑本身,但是會保證這路徑是唯一的。然後,將所有的邊權重加起來,得到這個圖的總權重。接着,我們使用折半搜索算法找出這條最短路徑的權重:是否有權重輕於的路徑? ;是否有權重輕於的路徑? …等等。找到最短路徑的權重之後,我們藉由以下演算法確定特定某個邊是否在這個路徑上:修改的權重為之後,詢問這個圖是否還是有一個權重為的哈密頓路徑?如果修改後的圖裏面不存在這條路徑,則這個邊必定在原圖的最短路徑裏面,反之,如果修改後此路徑還是存在,則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

參見