信念改訂（しんねんかいてい、、信念変化（）とも）は、新たに得られた情報を考慮に入れるために自らの信念を変化させる過程である。信念改訂の論理的形式化は、哲学、データベース、および合理的な知的エージェントの設計のために人工知能の分野で研究されている。
信念改訂を自明でないものにしているのは、この操作を実行するのに複数の異なる仕方が可能でありうるという点である。たとえば、現在の知識が「 は真である」「 は真である」「 と がともに真ならば は真である」という三つの事実を含んでいるとき、新情報「 は偽である」を導入して整合性を保つには、三つの事実のうち少なくとも一つを除去しなければならない。この場合、改訂を行う仕方は少なくとも三通り存在する。一般に、知識を変化させる仕方は複数ありうる。
改訂と更新 通常、二種類の変化が区別される。
更新（update） 新情報は現時点の状況に関するものであり、古い信念は過去の状況に言及する。更新は、変化を考慮に入れて古い信念を変化させる操作である。 改訂（revision） 古い信念と新情報の双方が同じ状況に言及する。新旧情報の間の非整合は、古い情報が新しい情報よりも信頼性が低い可能性によって説明される。改訂は、非整合を生じさせずに新情報を古い信念の集合に組み込む過程である。
信念改訂の主要な想定は、変化の最小性である。すなわち、変化の前後の知識はできる限り似ていなければならない。更新の場合、この原理は慣性の仮定を形式化する。改訂の場合、この原理は変化によってできる限り多くの情報を保存することを強制する。
例 以下の古典的な例は、更新と改訂の二つの設定において実行すべき操作が同一ではないことを示している。信念集合 と新情報 の二つの異なる解釈に基づく。
更新 このシナリオでは、二つの人工衛星ユニット A とユニット B が火星の周りを周回している。両衛星は着陸中に自らの状態を地球に送信するようプログラムされている。地球はそのうち一つの衛星から、まだ軌道上にあるという通信を受け取った。しかし干渉のため、どちらの衛星が信号を送ったかは不明である。その後、地球はユニット A が着陸したという通信を受け取る。このシナリオは次のようにモデル化できる。すなわち二つの命題変数 と がそれぞれユニット A と B がまだ軌道上にあることを表す。初期信念集合は （二機の衛星のいずれかがまだ軌道上にある）、新情報は （ユニット A は着陸しており、したがって軌道上にはない）である。更新の唯一の合理的な結果は である。二機のうち一機がまだ着陸していないという初期情報がユニット A のものだった可能性もあるため、ユニット B の位置は不明となる。 改訂 戯曲『作者を探す六人の登場人物』が二つある地元の劇場のいずれかで上演される。この情報は と表せる。ここで と はそれぞれ第一の劇場、第二の劇場での上演を表す。「ジーザス・クライスト・スーパースター」が第一の劇場で上演されるという追加情報は が成立することを示す。この場合、自明な結論は『作者を探す六人の登場人物』が第二の劇場で上演され、第一の劇場では上演されないというものであり、これは論理的には と表される。
この例は、信念 を新情報 で改訂すると、設定が更新か改訂かに応じて と という二つの異なる結果が生じることを示している。
縮約・拡大・改訂・整理・統合 すべての信念が同じ状況に言及する設定では、実行できる操作の間で次のような区別がなされる。
縮約（contraction） 信念の除去。 拡大（expansion） 整合性の確認なしに信念を追加すること。 改訂（revision） 整合性を維持しつつ信念を追加すること。 抽出（extraction） 整合的な信念集合ないしの順序を取り出すこと。 整理（consolidation） 信念集合の整合性を回復すること。 統合（merging） 整合性を維持しつつ二つ以上の信念集合を融合すること。
改訂と統合は次の点で異なる。前者は、組み込むべき新しい信念が古いものよりも信頼性が高いとみなされる場合に行われるため、古い信念の一部を除去することによって整合性を維持する。統合はより一般的な操作であり、信念集合間の優先順位は同一であってもなくてもよい。
改訂は、まず新しい事実を組み込み、その後整理を通じて整合性を回復させることによっても実行できる。これは、新情報が必ずしも古い知識より信頼性が高いものとして扱われないため、実際には改訂というよりむしろ統合の一形態である。
AGM 公準 AGM 公準（提唱者アルシュロン、、にちなむ）は、改訂を行う演算子が合理的とみなされるために満たすべき性質である。想定される設定は改訂の設定、すなわち同じ状況に言及する複数の情報が与えられる場合である。三つの操作が考慮される。すなわち、拡大（整合性の確認なしに信念を追加）、改訂（整合性を維持しつつ信念を追加）、縮約（信念の除去）である。
最初の六つの公準は「基本 AGM 公準」と呼ばれる。アルシュロン、ゲルデンフォルス、マキンソンが想定した設定では、現在の信念集合は論理式の集合 （信念集合、belief set）で表され、新情報は論理式 であり、改訂は現在の信念と新情報を被演算子にとり、改訂の結果を表す信念集合を返す二項演算子 によって行われる。 は拡大を表す。 は の演繹的閉包である。改訂に関する AGM 公準は以下の通りである。
閉性（Closure）: は信念集合（すなわち演繹的に閉じた論理式の集合）である。 成功（Success）: 包含（Inclusion）: 空虚性（Vacuity）: もし ならば 整合性（Consistency）: が矛盾するのは が矛盾するときに限る 外延性（Extensionality）: もし と が論理的同値ならば 超拡大（Superexpansion）: 亜拡大（Subexpansion）: もし ならば
八つの公準すべてを満たす改訂演算子として全会一致改訂（full meet revision）があり、そこでは が整合であれば と等しく、そうでなければ の演繹的閉包と等しい。この改訂演算子は AGM 公準をすべて満たすものの、改訂用論理式がそれと矛盾する場合には旧知識ベースからの情報が一切保持されないため、あまりに保守的すぎるとみなされてきた。
AGM 公準と同値な条件 AGM 公準は改訂演算子に対する複数の異なる条件と同値である。特に、選択関数、認識論的定着、球体系、選好関係と呼ばれる構造によって改訂演算子が定義可能であることと同値である。選好関係は、モデル集合上で反射的、推移的、完全な関係である。
AGM 公準を満たす各改訂演算子 は選好関係の族 （各可能な信念集合 に対して一つずつ）に対応し、 のモデルは におけるすべてのモデルの最小元にちょうど一致する。改訂演算子とそれに対応する順序族の関係は、 が、 に関する のすべての最小モデルを含むモデル集合を持つ論理式の集合であるという事実によって表現される。この条件は、 のモデル集合が順序 に関する の最小モデルの集合とちょうど一致することと同値である。
選好順序 は、想定可能ではあるが現時点では偽とみなされているものを含む、あらゆる状況の間の不もっともらしさの順序を表す。そうした順序に関する最小モデルは、知識ベースのモデル、すなわち現時点で最ももっともらしいとみなされているモデルにちょうど等しい。他のすべてのモデルはこれらより大きく、実際にもっともらしくないとみなされる。一般に、 は、モデル が表す状況がモデル が表す状況よりももっともらしいと信じられていることを示す。したがって、 と をモデルとする論理式による改訂においては、 のみを改訂後の知識ベースのモデルとして選ぶべきである。なぜなら、 は によって支持される諸シナリオの中で最ももっともらしいシナリオを表すからである。
縮約 縮約は、知識ベース から信念 を除去する操作であり、その結果を と表す。改訂と縮約の演算子は、レビとハーパーの恒等式によって関係づけられる。
縮約に対しても八つの公準が定義されている。ある改訂演算子が改訂の八公準を満たすときは常に、それに対応する縮約演算子も縮約の八公準を満たし、逆も成り立つ。ある縮約演算子が縮約公準の少なくとも最初の六つを満たすならば、上記二つの恒等式によりそれを改訂演算子に変換し、再び縮約演算子に戻すと、もとの縮約演算子が得られる。改訂演算子から出発した場合も同様である。
縮約の公準のなかで長らく議論されてきたのが、回復（recovery）公準である。
この公準によれば、信念 を除去した後で同じ信念を信念集合に再導入すると、もとの信念集合に戻るはずである。しかしそうしたふるまいが必ずしも合理的でない例がいくつか存在する。特に、 のような一般的な条件による縮約は、 のようなより特殊な条件を信念集合から除去することにつながる。したがって、 を再導入することがより特殊な条件 の再導入にもつながるべきである理由は明らかでない。たとえば、以前ジョージがドイツ国籍を持つと信じられていたなら、彼はヨーロッパ人であるとも信じられていた。この後者の信念を縮約することは、ジョージがヨーロッパ人であると信じるのをやめることに等しく、したがって彼がドイツ国籍を持つという信念もまた信念集合から取り下げられる。その後ジョージがオーストリア国籍を持つと判明すれば、彼がヨーロッパ人であるという事実も再導入される。しかし回復公準によれば、彼がドイツ国籍も持つという信念もまた再導入されるべきである。
レビとハーパーの恒等式によって導かれる改訂と縮約の対応関係は次のようになる。すなわち、回復公準を満たさない縮約は、八公準すべてを満たす改訂に翻訳され、八公準すべてを満たす改訂は、回復を含む八公準すべてを満たす縮約に翻訳される。その結果、回復を除外して考えれば、複数の縮約演算子が単一の改訂演算子に翻訳され、それは再び唯ひとつの縮約演算子に翻訳される。この演算子は、はじめの縮約演算子群のうち回復を満たす唯一のものであり、この群のなかで最も多くの情報を保存する演算子である。
ラムゼー・テスト
反事実的条件文 の評価は、ラムゼー・テスト（フランク・P・ラムゼイにちなむ）に従って、現在の信念集合に を仮定的に追加したうえで の真偽を確認することによって行うことができる。 が現在保持されている信念集合であれば、ラムゼー・テストは次の対応関係によって形式化される。
であるのは であるとき、かつそのときに限る。
信念を表す論理式の対象言語が命題論理の場合、ラムゼー・テストは信念改訂演算子を用いた反事実的条件文の整合的な定義を与える。しかし信念を表す論理式の言語自体が反事実的条件結合子 を含む場合、ラムゼー・テストからいわゆる「ゲルデンフォルスの自明性結果」が導かれる。すなわち、改訂に関する AGM 公準とラムゼー・テストの条件をともに満たす自明でない改訂演算子は存在しない。この結果は、 のような反事実的な論理式が信念集合や改訂用論理式に含まれうるという想定の下で成立する。この問題に対しては複数の解決策が提案されている。
非単調推論関係 固定された知識ベース と改訂演算子 が与えられたとき、次の定義によって非単調推論関係を定義できる。すなわち、 であるのは、 であるとき、かつそのときに限る。言い換えれば、論理式 が別の論理式 を含意するのは、当該論理式を現在の知識ベースに追加すると が導出されるときである。この推論関係は非単調である。
AGM 公準はこの推論関係に対する公準集合に翻訳できる。これらの公準はいずれも、非単調推論関係について従来考察されてきた公準集合のいずれかから導かれる。逆に、非単調推論関係について考慮されてきた条件は改訂演算子に対する公準に翻訳できる。これらすべての公準は AGM 公準から導かれる。
基礎付け的改訂 AGM の枠組みでは、信念集合は演繹的に閉じた命題論理式の集合として表される。そのような集合は無限であるが、常に有限に表現可能である。しかし演繹的に閉じた論理式集合を扱うと、改訂において同値な信念集合は同一とみなすべきであるという想定が暗黙のうちに導入される。これは「構文の無関係性原理」と呼ばれる。
この原理は議論され続けている。すなわち、 と は同値な二つの集合であるが、 による改訂は異なる結果をもたらすべきである。第一の場合、 と は分離した二つの信念であり、したがって による改訂は に何らの影響も及ぼすべきでなく、改訂結果は となる。第二の場合、 は単一の信念として捉えられる。 が偽であるという事実はこの信念と矛盾するため、当該信念は信念集合から除去されるべきである。したがってこの場合の改訂結果は となる。
演繹的に閉じた知識ベースを用いる問題は、それ自体として知られている知識と、それらの単なる帰結にすぎない知識との区別がつけられない点にある。この区別は、代わりに信念改訂への「基礎付け」的アプローチによってなされる。基礎付け的アプローチは哲学における基礎付け主義と関係している。このアプローチによれば、非派生的な知識を撤回することは、他の非派生的な知識によって別途支持されていない当該知識のすべての帰結の撤回に至るべきである。このアプローチは、演繹的に閉じていない知識ベースを用い、そこに含まれるすべての論理式が自立した信念（派生的でない信念）を表すと想定することによって実現される。信念改訂の基礎付け的アプローチと演繹的に閉じた知識ベースに基づくアプローチを区別するために、後者は「コヒーレンス」的アプローチと呼ばれる。この名称は、コヒーレンス的アプローチが自立信念と派生信念の双方を含むすべての信念間のコヒーレンス（整合性）の回復を目指すために選ばれている。このアプローチは哲学におけるコヒーレンス主義と関係している。
演繹的に閉じていない信念集合上で作動する基礎付け的改訂演算子は、典型的には、 と整合な の部分集合を選び、何らかの仕方で結合し、それらを と連言でつなぐ。以下は演繹的に閉じていない基底改訂演算子の二例である。
WIDTIO（When in Doubt, Throw it Out） と整合な の極大部分集合の交わりを取り、そこに を追加する。言い換えれば、改訂の結果は、、および と整合な のすべての極大部分集合に含まれる のすべての論理式によって構成される。 ウィリアムズ（） 有限基底に対して AGM の改訂・縮約操作を実行することを可能にする新しい表現を開発することによって未解決問題を解決した。この表現は計算モデルに翻訳され、信念改訂のためのが開発された。 Ginsberg–Fagin–Ullman–Vardi を含み、かつ整合的な の極大部分集合を選言で結合する。 Nebel 上と類似するが、論理式間に優先順位を与えることができるため、優先順位の高い論理式は低い論理式よりも取り下げられにくくなる。
信念改訂の基礎付け的アプローチのもう一つの実現形態は、信念間の依存関係を明示的に宣言することに基づく。では、信念間の依存リンクを指定できる。言い換えれば、ある事実が他の一つないし複数の事実に基づいて信じられていると明示的に宣言できる。そのような依存性を「正当化（justification）」と呼ぶ。正当化を持たない信念は、演繹的に閉じていない知識ベースアプローチにおける非派生信念の役割を果たす。
モデルに基づく改訂と更新 関与する論理式のモデル集合に基づく改訂・更新の複数の提案が、AGM の枠組みとは独立に開発されてきた。このアプローチの背景にある原理は、知識ベースは可能世界の集合、すなわち当該知識ベースに照らしてありうるとされる諸シナリオの集合と同値であるというものである。したがって改訂は、対応する知識ベース上ではなく可能世界集合上で行うことができる。
モデルに基づく改訂・更新演算子は、通常、その提唱者の名前で呼ばれる。すなわちウィンスレット、フォーバス、佐藤、、ヘグナー、ウェーバーである。これら最初の四つの提案では、論理式 を別の論理式 で改訂/更新した結果は、 のモデルに最も近い のモデル集合によって特徴づけられる。近さの異なる概念を定義できるため、これらの提案間には差異が生じる。
ペッパスとウィリアムズ 改訂と更新の間の形式的関係を提供した。両者は にウィンスレット恒等式を導入した。 ダラル のモデルとのハミング距離が最小である のモデルが、変更の結果得られるモデルとして選ばれる。 佐藤 ダラルと類似するが、二つのモデル間の距離は、それらによって異なる値を与えられるリテラルの集合として定義される。モデル間の類似性はこれらの差異の集合包含として定義される。 ウィンスレット の各モデルに対して、最も近い のモデルが選ばれる。比較は差異の集合包含によって行われる。 ボルギダ と が矛盾する場合はウィンスレットと同じ。そうでない場合、改訂結果は となる。 ウィンスレットと類似するが、ハミング距離を用いる。
ヘグナーが定義する改訂演算子は、 に言及される変数の値に が影響を与えないようにする。この操作の結果は と整合な論理式 であり、したがって と連言でつなぐことができる。ウェーバーによる改訂演算子は類似するが、 から除去されるリテラルは のすべてのリテラルではなく、佐藤の近さ尺度による と の最も近いモデル対によって異なる値を与えられるリテラルのみである。
反復改訂 AGM 公準は、あらゆる知識ベース に選好順序（モデル上の順序）を対応させることと同値である。しかし AGM 公準は、同値でない二つの知識ベースに対応する順序どうしを関係づけない。特に、知識ベース と改訂版 に対応する順序は完全に異なりうる。これは二度目の改訂を行う際の問題である。というのも、 を計算するためには に対応する順序が必要となるからである。
しかしながら、 と に対応する順序どうしの関係を確立することはこの問題の正しい解決策ではないと認識されてきた。実際、選好関係は結果の知識ベースだけでなく、これまでの改訂の履歴に依存するべきである。より一般に、選好関係はエージェントの心的状態について単なる知識ベースよりも多くの情報を与える。実際、二つの心的状態は同じ知識 を表しつつも、新しい知識をどのように取り込むかにおいて異なりうる。たとえば二人の人物が休暇の行き先について同じ考えを持っていても、100万ドルの宝くじに当たった場合にこの考えをどう変えるかは異なりうる。選好順序の基本条件はその最小モデルが対応する知識ベースのモデルにちょうど等しいというものであるため、知識ベースは選好順序によって暗黙のうちに表現されるとみなすことができる（ただしその逆は成り立たない）。
選好順序があれば対応する知識ベースを導出できると同時に、一段階の改訂も実行できることから、反復改訂に関する研究は、改訂に応じて選好順序をどのように変化させるべきかに集中してきた。一段階の改訂が知識ベース をどのように新しい知識ベース に変化させるかを扱うのに対し、反復改訂は、選好順序（現在の知識と、偽と信じられている状況をどの程度可能とみなしているかの双方を表す）を、 が学習されたときにどのように新しい選好関係へと変化させるかを扱う。反復改訂の一段階はさらなる改訂を可能にする新しい順序を生成する。
通常、二種類の選好順序が想定される。数値的なものと非数値的なものである。前者では、モデルのもっともらしさの水準は非負整数によって表される。ランクが低いほど、モデルに対応する状況がもっともらしい。非数値的選好順序は AGM の枠組みで用いられる選好関係、すなわちモデル上の全順序（となりうる順序）に対応する。非数値的選好関係は当初、反復改訂には不適とみなされていた。なぜなら、数値の場合には可能な、複数の他の改訂によって改訂を反転させることが不可能だからである。
ダーウィッシュとパールは反復改訂について次の公準を定式化した。
ならば ならば ならば ならば
具体的な反復改訂演算子はシュポーン、ブティリエ、ウィリアムズ、レーマンらによって提案されている。ウィリアムズはまた、一般的な反復改訂演算子も提示した。
シュポーンの棄却された改訂 この非数値的な提案は最初にシュポーンによって考察されたが、シュポーン自身は、改訂がいくつかの順序を変えると他の改訂の系列によっては元の順序が回復できなくなるという事実に基づき、この演算子を却下した。この演算子は、新情報 を踏まえて選好順序を変化させるさい、 のすべてのモデルが他のあらゆるモデルより優先されるようにする。二つのモデルがいずれも のモデルであるか、いずれも のモデルでない場合には、元の選好順序が維持される。 自然改訂（Natural revision） 論理式 によって選好順序を改訂するさい、（選好順序による） のすべての最小モデルが他のすべてのモデルより優先されるようにする。 の最小モデルでない二つのモデルを比較するときは、元のモデル間の順序が保持される。この演算子は、 による改訂後の知識ベースのモデルが選好順序による の最小モデルであるという性質を維持しつつ、モデル間の順序を最小限に変化させる。 変換（Transmutations） ウィリアムズは変換を用いた信念改訂反復の最初の一般化を提示した。ウィリアムズは、数値的な選好順序上で動作する条件化と調整という二種類の改訂を用いて変換を例示した。改訂は論理式だけでなく、既存信念のもっともらしさの度合いを示す数値ないしランクをも要求する。選好順序はなお反転させられているが（ランクが低いほどモデルはもっともらしい）、改訂用論理式のもっともらしさの度合いは直接的である（度合いが高いほど論理式がより信じられている）。 ランク付き改訂（Ranked revision） 最初にモデルへの非負整数の割り当てであるランク付きモデルを指定しなければならない。このランクは選好順序と類似しているが、改訂によっては変化しない。改訂の系列によって変化するのは、現在のモデル集合（現在の知識ベースを表す）と系列のランクと呼ばれる数である。この数は単調非減少にしか変化しえないため、いくつかの改訂系列は以降のあらゆる改訂が全会一致改訂として実行される状況につながる。
統合 改訂演算子に暗黙に含まれる想定は、新情報 が常に旧知識ベース よりも信頼性が高いとみなされるというものである。これは AGM 公準の第二番目「 は を で改訂した後に常に信じられる」によって形式化される。より一般に、二つではなく複数の情報片を統合する過程を、それらが同じ信頼性を持つ場合と持たない場合の双方で考察できる。信頼性の低い情報片 がより信頼性の高い と統合される場合、改訂はこの過程の特殊例となる。
改訂過程への入力が論理式の対 と であるのに対し、統合への入力は論理式の多重集合 , , … である。多重集合の使用は、統合過程への二つの情報源が同一でありうるため必要となる。
同じもっともらしさの度合いを持つ複数の知識ベースを統合するさい、仲裁（arbitration）と多数決（majority）の区別がなされる。この区別は、情報についてなされる想定と、それらをどのように結合すべきかに依存する。
仲裁 二つの知識ベース と の仲裁の結果は を含意する。この条件は、旧情報をできる限り多く維持するという想定を形式化する。というのも、両方の知識ベースが含意する任意の論理式は仲裁の結果によっても含意されなければならないと課すことに等しいからである。可能世界の見方では、「現実」の世界は二つの知識ベースの少なくとも一方に照らして可能とみなされる世界のひとつと想定される。 多数決 知識ベース と他の知識ベースを統合する結果は、 と同値な十分な数の他の知識ベースを追加することによって を含意させることができる。この条件は、多数決による投票に対応する。すなわち、十分な数の知識ベースは、任意の固定された知識ベース集合の「意見」を常に上回りうる。
上記は仲裁の元来の定義である。より新しい定義によれば、仲裁演算子は統合すべき同値な知識ベースの数に対して不感な統合演算子である。この定義は仲裁を多数決の正反対のものにする。
仲裁と統合の双方について公準が提案されている。すべての公準を満たす仲裁演算子の例が古典的な選言である。すべての公準を満たす多数決演算子の例は、統合すべき知識ベースのモデルとの総ハミング距離が最小となるすべてのモデルを選ぶものである。
統合演算子はモデル上の順序の族として表現できる（統合すべき知識ベースの多重集合に対して一つずつ）。すなわち、知識ベースの多重集合を統合した結果のモデルは、その多重集合に対応する順序の最小モデルである。このように定義された統合演算子が統合の公準を満たすのは、順序族が所与の条件の集合を満たすとき、かつそのときに限る。仲裁の古い定義については、順序はモデル上ではなくモデルの対（一般にはタプル）上のものになる。
社会選択理論 多くの改訂の提案は、可能な選択肢の相対的なもっともらしさを表すモデル上の順序を含む。統合の問題は、諸順序集合を一つの順序、すなわち選択肢を統合した際のもっともらしさを表す順序に結合することに帰着する。これは社会選択理論で行われることと類似している。社会選択理論は、エージェント集団の選好をどのように合理的に結合しうるかを研究する。信念改訂と社会選択理論は、順序集合を一つの順序に結合する点で類似する。両者の違いは、これらの順序が社会選択理論では選好として、信念改訂ではもっともらしさとして解釈される点にある。もう一つの違いは、選択肢が社会選択理論では明示的に列挙されるのに対し、信念改訂では所与のアルファベット上の命題モデルとされる点である。
計算量 計算量の観点から、信念改訂について最もよく研究されている問題は命題論理における問合せ応答である。これは、論理式が改訂の結果に含意されるか、すなわち （ここで 、、 は命題論理式）を判定する問題である。より一般に、問合せ応答は、論理式が信念改訂の結果によって含意されるかを判定する問題であり、これは更新、統合、改訂、反復改訂などでありうる。もう一つの関心を集めた問題はモデル検査である。すなわち、モデルが信念改訂の結果を満たすかどうかを検査する問題である。関連する問いは、そのような結果がその引数の空間の多項式空間内で表現できるかどうかである。
演繹的に閉じた知識ベースは無限であるため、演繹的に閉じた知識ベース上で作動する信念改訂演算子の計算量研究は、そのような演繹的に閉じた知識ベースが同値な有限知識ベースの形で与えられるという想定の下で行われる。
信念改訂の演算子と信念改訂の枠組み（scheme）は区別される。前者は論理式の対を別の論理式に写す単純な数学的演算子であるのに対し、後者は選好関係のような追加情報に依存する。たとえば、ダラルの改訂は演算子である。二つの論理式 と が与えられれば、 を計算するのに他の情報は必要ない。他方、選好関係に基づく改訂は枠組みである。なぜなら、モデル間の選好順序の族が与えられなければ と だけでは改訂結果を決定できないからである。改訂枠組みの計算量は、改訂の計算に必要な追加情報がなんらかのコンパクトな形式で与えられるという想定の下で決定される。たとえば、選好関係はモデルが順により選好されるような論理式の系列で表現できる。関係をモデルの対の集合として明示的に格納することは、命題文字数に対して指数関数的な空間を要するため、選好のコンパクトな表現ではない。
命題論理における問合せ応答とモデル検査の計算量は、ほとんどの信念改訂演算子と枠組みで多項式階層の第二レベルに属する。ほとんどの改訂演算子は表現の爆発の問題を抱える。すなわち、二つの論理式を改訂した結果は、必ずしも二つの元の論理式の空間の多項式空間で表現できるとは限らない。言い換えれば、改訂は知識ベースのサイズを指数関数的に増大させうる。
関連性