推移閉包
計算複雑性理論において、複雑性クラス NL は一階述語論理に推移閉包を追加した論理で表される論理式と正確に対応している。これは、推移閉包の属性が NL完全な問題である STCON 問題(グラフ内の経路を求める問題)と密接に関係しているためである。同様にクラス Lは、一階述語論理に可換な推移閉包を加えたものである。推移閉包を二階述語論理に加えると、PSPACEが得られる。