目录
功能性問題
在計算複雜性理論內，功能性問題或者函式問題（function problem）是一種計算問題（:en:computational problem），我們對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這麼單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。 因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而FNP是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。 對所有能在多項式時間內解決的的功能性問題，一定存在一個雷同的決定型問題，可以用多項式時間圖靈歸約將後者歸約為前者的方式，解決這個功能性問題。舉例，旅行推銷員問題的決定型問題版本如下： 給定這個決定性問題的解答，我們則可以解決旅行推銷員問題如下： 這個演算法將旅行推銷員問題的時間複雜度放進FPNP內（可以在多項式時間之內，以決定性圖靈機和一個能解決NP問題的神諭解決的問題），並且事實上是這個複雜度類的完備問題。.
对数
在数学中，真数 x（对于底数 ）的对数是 y 的指数 y，使得 。底数 的值一定不能是1或0（在扩展到复数的复对数情况下不能是1的方根），典型的是、 10或2。数x（对于底数β）的对数通常写为 稱作為以β為底x的對數。 当x和β进一步限制为正实数的时候，对数是1个唯一的实数。 例如，因为 我们可以得出 用日常语言说，以3为底81的对数是4。.
查看 L (複雜度)和对数
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
查看 L (複雜度)和图灵机
萨维奇定理
萨维奇定理（）是计算复杂性理论中的一个定理，由沃尔特·萨维奇（Walter Savitch）于1970年证明。定理的结论为对于任何函数f(n)满足f(n)\geq \log n，下列关系成立： 亦即，如果一台非确定型图灵机能够利用f(n)空间解决某个问题，那么一台确定型图灵机能够在至多f^2(n)空间解决相同的问题。尽管非确定性的引入能够在时间上带来指数的提升，但是，这种引入对于空间而言作用有限。.
非确定型图灵机
如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合，\Gamma是带字母表，L, R分别表示读写头向左和向右移动；符号2^ 表示集合A的幂集，即 2^A.
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
另见
複雜度類
- 2-EXPTIME
- ALL (複雜度)
- DLOGTIME
- DTIME
- E (複雜度)
- ELEMENTARY
- EXPSPACE
- EXPTIME
- L (複雜度)
- NC (复杂度)
- NE (複雜度)
- NEXPTIME
- NL (複雜度)
- NL完全
- NP (複雜度)
- NP-易
- NP困难
- NP完全
- NSPACE
- NTIME
- P (複雜度)
- P-完全
- PH (複雜度)
- PR (複雜度)
- PSPACE
- PolyL
- R (複雜度)
- RE (複雜度)
- SC (複雜度)
- UP (複雜度)
- 伪多项式时间
- 反NP
- 指數譜系
- 算数阶层
- 複雜度類
- 複雜度類列表
- 隨機存取圖靈機
亦称为 Co-SL，FL (复杂度)，LSL，Log-空间规约，NL (複雜度)，NL-完全，NLC，RL (複雜度)，SL (複雜度)，SL完全，反SL，对数空间，對數空間歸約。