低 (複雜度)

在計算複雜度理論內，若有A與B兩個複雜度類，且AB = A；或者說, A 在B成為他的神諭之後的複雜度等同於A，則我們說複雜度類別B比A要來的"低"。這陳述代表著一個可以解決問題類別A的機器，在獲得了在單位時間內解決問題類別B的能力之後，並沒有增加多餘的計算能力。特別是，這代表著如果B類別低於A類別，則B必然包含在A裡面。

較不正式的說，較低的關係不僅僅代表包含於B的問題可以被能夠解決A問題的機器所解決, 而且是"可以被簡單解決的"。一個能解決A問題類別的機器可以模擬許多計算B的啟示，而不超出其計算能力的上限值。

建立在一個類別低於另一類別的關係跟結果常常被稱呼為""。

Category:機率複雜度類