功能性問題

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

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

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

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

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

令${\displaystyle n}$為邊的數量，${\displaystyle w_{i}}$則是邊${\displaystyle i}$的權重。首先我們重新設定邊的權重，給予每個邊${\displaystyle i}$新的權重${\displaystyle w'_{i}=2^{(n+1)}w_{i}+2^{i}}$。這並不會改變最短路徑本身，但是會保證這路徑是唯一的。然後，將所有的邊權重加起來，得到這個圖的總權重${\displaystyle M}$。接著，我們使用折半搜索算法找出這條最短路徑的權重：是否有權重輕於${\displaystyle <M/2}$的路徑？；是否有權重輕於${\displaystyle <M/4}$的路徑？…等等。找到最短路徑的權重${\displaystyle W}$之後，我們藉由以下演算法確定特定某個邊${\displaystyle i}$是否在這個路徑上：修改${\displaystyle i}$的權重為${\displaystyle W+1}$之後，詢問這個圖是否還是有一個權重為${\displaystyle W}$的哈密頓路徑？如果修改後的圖裡面不存在這條路徑，則${\displaystyle 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

相關條目

最佳化問題