函數問題

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

因為沒有明顯類比的語言，函數問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，函數問題歸約的過程也比較微妙。函數問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說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不在原來的路徑之內。

這個演算法將旅行推銷員問題的時間複雜度放進FP^NP內（可以在多項式時間之內，以決定性圖靈機和一個能解決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

參見[編輯]