計算複雑性との関連
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 13:38 UTC 版)
計算複雑性理論において、複雑性クラス NL は一階述語論理に推移閉包を追加した論理で表される論理式と正確に対応している。これは、推移閉包の属性が NL完全な問題である STCON 問題（グラフ内の経路を求める問題）と密接に関係しているためである。同様にクラス Lは、一階述語論理に可換な推移閉包を加えたものである。推移閉包を二階述語論理に加えると、PSPACEが得られる。
※この「計算複雑性との関連」の解説は、「推移閉包」の解説の一部です。
「計算複雑性との関連」を含む「推移閉包」の記事については、「推移閉包」の概要を参照ください。
ウィキペディア小見出し辞書の「計算複雑性との関連」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 計算複雑性との関連のページへのリンク
