跳至內容

低 (複雜度)

維基百科,自由的百科全書

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

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

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