基本介紹
- 中文名：函式問題
- 外文名：function problem
簡介,計算複雜性理論,決定性問題,相關條目,
簡介
在計算複雜性理論內，功能性問題或者函式問題（function problem）是一種計算問題（en:computational problem），我們對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這么單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。
因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而FNP是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。
計算複雜性理論
計算複雜性理論（Computational complexity theory）是理論計算機科學和數學的一個分支，它致力於將可計算問題根據它們本身的複雜性分類，以及將這些類別聯繫起來。一個可計算問題被認為是一個原則上可以用計算機解決的問題，亦即這個問題可以用一系列機械的數學步驟解決，例如算法。
如果一個問題的求解需要相當多的資源（無論用什麼算法），則被認為是難解的。計算複雜性理論通過引入數學計算模型來研究這些問題以及定量計算解決問題所需的資源（時間和空間），從而將資源的確定方法正式化了。其他複雜性測度同樣被運用，比如通信量（套用於通信複雜性），電路中門的數量（套用於電路複雜性）以及中央處理器的數量（套用於並行計算）。計算複雜性理論的一個作用就是確定一個能或不能被計算機求解的問題的所具有的實際限制。
在理論計算機科學領域，與此相關的概念有算法分析和可計算性理論。兩者之間一個關鍵的區別是前者致力於分析用一個確定的算法來求解一個問題所需的資源量，而後者則是在更廣泛意義上研究用所有可能的算法來解決相同問題。更精確地說，它嘗試將問題分成能或不能在現有的適當受限的資源條件下解決這兩類。相應地，在現有資源條件下的限制正是區分計算複雜性理論和可計算性理論的一個重要指標：後者關心的是何種問題原則上可以用算法解決。
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：“給兩個數字x與y，x是否可以整除y？”便是決定性問題，此問題可回答是或否，且依據其x與y的值。
決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：“給予一個正整數x，則哪些數可整除x？”
另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。
解決決定性問題的方法稱為決策程式或算法。一個針對決定性問題的算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些算法所解決，則稱此問題可決定。
計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。
計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。
相關條目
- 最佳化問題
