代数論理と論理計算の複雑さの関係?

私は代数論理について少し学んでいますし、与えられた論理の代数的意味を知ることが、計算そのものから論理そのものを研究するのに役立つかもしれないと思っていました。

特に、その代数的意味論について推論することによって得られたいくつかの論理についての充足可能性問題の複雑さ(または決定可能性)の結果の例はありますか?

例えば命題論理の意味論はブール代数の形で与えられる。それらとSATが決定可能で$ NP
$完全であるという事実との間には何らかの関係がありますか?

ベストアンサー

あなたが与えた例は次のように拡張されます:

  • 任意の格子(任意の格子で充足可能な所定の数式)のSATは、多項式時間決定可能である
  • モジュラーラティスのSATは固定できません: Freese、Ralphフリーモジュラー格子 、Trans。
    Am。数学。 Soc。 261、81-91(1980)に記載されている。 ZBL0437.06006
  • ブール代数のSATがNP完全である

モジュラ格子はブール代数と任意の格子の間にありますが、最も複雑です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です