函式複雜性類(complexity class of functions )一種複雜性類，具體來說是指由一些具有“相似”複雜性的遞歸。
基本介紹
- 中文名：函式複雜性類
- 外文名：complexity class of functions
- 學科：數學
詳解,複雜度類之間的關係,薩維奇的定理,其他關係,
詳解
在計算複雜度理論中，一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下形式：可以被同一個抽象機器M使用O(f(n))的資源R所解決的問題的集合（n是輸入數據的大小）。
例如NP類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題（Function problem）的集合，例如FP。
許多複雜度類可被描述它的數學邏輯（mathematical logic）特徵化，請見可描述的複雜度（descriptive complexity）。而Blum公理用於不需實際計算模型就可定義複雜度類的情況。
複雜度類之間的關係
薩維奇的定理
Savitch定理確定PSPACE=NPSPACE和EXPSPACE=NEXPSPACE。複雜性理論的一個核心問題是非確定性是否為計算模型增加了重要的力量。這是時間背景下開放P與NP問題的核心。Savitch定理表明，對於空間，非確定性並不會顯著增加更多的權力，其中“重要”意味著多項式和超多項式資源需求之間的差異（或者，對於EXPSPACE，指數和超指數之間的差異）。例如，Savitch定理證明，對於確定性圖靈機，不需要指數空間的問題可以通過非確定多項式空間圖靈機來解決。
其他關係
如果類別X是類別Y的子集合，則X將會畫在Y底下，並以一黑線相連。如果X是子集合，但不知是否與Y相等，則以較輕的虛線相連。實際上可解與不可解問題更屬於可計算性理論，但是它有助於更透徹了解複雜度類的問題。
