Loading AI tools
来自维基百科,自由的百科全书
在計算複雜性理論內,函數問題(英語:Function problem)或者功能性問題是一種計算問題,對任何一種輸入都預期會有單一個輸出,但是輸出不像是決定性問題一樣這麼單純。換句話說,輸出不只是或否,比決策問題複雜得多。重要的範例像是旅行推銷員問題,詢問一張圖是否有可以繞過每一點的不重複路徑(輸出為路徑),以及整數分解,輸出為輸入的質因數。
因為沒有明顯類比的語言,函數問題比起決定型問題要難以研究。而且因為輸出的可能變多,在解決輸入輸出之間的轉換,函數問題歸約的過程也比較微妙。函數問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機在多項式時間裡面可以解決的函數問題(類似於決定性問題的P),而FNP是指可以用非確定型圖靈機在多項式時間裡面可以解決的函數問題(類似於決定性問題的NP)。
對所有能在多項式時間內解決的的函數問題,一定存在一個雷同的決定型問題,可以用多項式時間圖靈歸約將後者歸約為前者的方式,解決這個函數問題。舉例,旅行推銷員問題的決定型問題版本如下:
給定這個決定性問題的解答,我們則可以解決旅行推銷員問題如下:
這個演算法將旅行推銷員問題的時間複雜度放進FPNP內(可以在多項式時間之內,以決定性圖靈機和一個能解決NP問題的神諭解決的問題),並且事實上是這個複雜度類的完備問題。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.