単調な二重化

理論計算機科学において、単調双対化は単調ブール関数の双対を構築する計算問題である。同等の問題は、与えられたハイパーグラフの横断ハイパーグラフを構築すること、集合族のすべての最小ヒット集合をリストすること、集合族のすべての最小集合被覆をリストすることとして定式化することもできる。これらの問題は、その入力と出力を合わせたサイズで準多項式時間で解くことができるが、多項式時間で解けるかどうかは未解決の問題である。

ブール関数は、入力として引数に真理値の割り当てを受け取り、出力として別の真理値を生成します。引数を偽から真に変更しても、出力が真から偽に変更されない場合、それは単調です。すべての単調ブール関数は、論理否定("not")を使用せずに、論理和("or") と論理積("and") のみを使用してブール式として表現できます。このような式は単調ブール式と呼ばれます。すべての単調ブール式は、単調ブール関数を表します。^[1]

同じ関数に対して、多くの異なる表現が存在する場合があります。その中には、連言正規形と選言正規形という2つの特別な表現があります。単調関数の場合、これら2つの特別な形式も単調に制限できます。^[1]

• 単調関数の連言正規形は、関数を節の連言 ("and") として表現します。各節は、いくつかの変数の選言 ("or") です。関数全体が真であるときはいつでも節が真である場合、連言正規形に節が現れることがあります。この場合、関数の真は節の真を意味するため、それは含意と呼ばれます。この表現は、最小の変数セットを使用する含意であるプライム含意のみを使用するように制限することで標準にすることができます。プライム含意のみを使用する連言正規形は、プライム CNFと呼ばれます。^[1]
• 単調関数の選言正規形は、関数を節の選言 ("or") として表現します。節のそれぞれは変数の連言 ("and") です。関数全体が偽であるときは常に、連言が偽である場合、選言正規形に連言が現れることがあります。この場合、連言が真であれば関数の真を意味するため、連言は含意子と呼ばれます。この表現は、最小の変数セットを使用する含意子であるプライム含意子のみを使用するように制限することで標準にすることができます。プライム含意子のみを使用する選言正規形は、プライム DNFと呼ばれます。^[1]

ブール関数の双対は、その変数すべてを否定し、関数を適用し、その結果を否定することで得られる。任意のブール関数の双対の双対は、元の関数である。単調関数の双対は単調である。単調なブール式が与えられた場合、すべての連言を選言に置き換えると、ド・モルガンの法則に従って、双対関数の別の単調なブール式が生成される。しかし、これにより連言正規形が選言正規形に変換され、逆もまた同様となるため、望ましくない結果になる可能性がある。単調双対化は、式の形式を変更せずに双対関数の式を見つける問題、または同等に、ある正規形の関数を双対形式に変換する問題である。^[1]

関数問題として、単調双対化は次のように同等に表現できる: ^{[1] [2]}

• （素）CNF式が与えられた場合、双対関数の（素）CNF式を構築します。^[1]
• 関数の（プライム）CNF式を同じ関数の（プライム）DNF式に変換する、またはその逆を行う^[1]
• 与えられたハイパーグラフの横断ハイパーグラフを構築します。これは、与えられたハイパーグラフのすべての辺に接する頂点の最小部分集合ごとにハイパーエッジを持つ、同じ頂点集合上のハイパーグラフです。^[1]
• 集合の族が与えられたとき、族のすべての最小ヒット集合を生成する。これらは、各集合から少なくとも1つの要素を含み、同じ特性を持つ適切な部分集合を持たない要素の集合である。与えられた族の集合がハイパーグラフのハイパーエッジとして解釈される場合、それらの最小ヒット集合は横断ハイパーグラフのハイパーエッジである。^[2]
• 集合族が与えられた場合、その族のすべての最小集合被覆を生成する。集合被覆は、族全体と同じ和集合を持つサブ族である。与えられた族内の集合がハイパーグラフの頂点として解釈され、集合の各要素がその要素を含む集合に付随するハイパーエッジとして解釈される場合、最小集合被覆は横断ハイパーグラフのハイパーエッジである。^[2]

この問題の別のバージョンは、計算学習理論における「正確な学習」の問題として定式化できます。単調なブール関数を評価するサブルーチンへのアクセスが与えられた場合、少数の関数評価を使用して、関数の CNF 表現と DNF 表現の両方を再構築します。ただし、この問題の複雑さを分析するには、CNF 表現と DNF 表現の両方が出力されることが重要です。未知の単調関数の CNF 表現のみが出力される場合、情報理論から、関数評価の回数は、入力と出力の合計サイズに対して指数関数になる必要があることがわかります。これは、(正しい答えを確実に得るために) アルゴリズムが各プライム含意に対して少なくとも 1 回、各プライム含意に対して少なくとも 1 回関数を評価する必要があるためですが、この評価回数はプライム含意の数だけよりも指数関数的に大きくなる可能性があります。^[1]

単調双対化問題の変形をブール値の答えを持つ決定問題として表現することも可能だ: ^[1]

• 2つの素数CNF式が双対関数を表すかどうかをテストする
• プライム CNF 式とプライム DNF 式が同じ関数を表すかどうかをテストします。

単調双対化に多項式時間アルゴリズム（これらの同等な形式のいずれか）があるかどうかは未解決の問題です。知られている最速のアルゴリズムは準多項式時間で実行されます。^[1] 双対化問題と正確な学習問題の出力のサイズは、変数の数または入力サイズの関数として、指数的に大きくなる可能性があります。たとえば、互いに素な三角形で構成される -頂点グラフには、横断ハイパーグラフにハイパーエッジがあります。^[3]したがって、これらの問題に必要なのは、出力節ごとに少し時間がかかる、出力に敏感なアルゴリズムです。 問題の決定、双対化、および正確な学習の定式化はすべて、次の意味で計算的に同等です。これらの問題のいずれも、他のいずれかのサブルーチンを使用して解決でき、サブルーチン呼び出しの数は、問題の入力と出力の合計サイズの多項式です。^{[4]したがって、これらの問題のいずれかが}多項式時間で解決できる場合、すべてが可能です。しかし、これらの問題に対する最も良い時間制限は準多項式時間であることが知られています。多項式時間で解けるかどうかは未解決の問題です。^[1]${\displaystyle n}$${\displaystyle n/3}$${\displaystyle 3^{n/3}}$

CNF 式として与えられた単調関数の双対関数の素 CNF 式を見つける問題は、与えられた関数の DNF 式を見つけてそれを双対化することで解決できます。したがって、双対 CNF 式を見つけることと、(素) 与えられた関数の DNF 式を見つけることは、同じ複雑さを持ちます。この問題は、問題の正確な学習定式化の特殊なケースと見なすこともできます。与えられた CNF 式から、それが表す関数を評価するのは簡単です。正確な学習アルゴリズムは、開始 CNF 式と目的の DNF 式の両方を返します。したがって、双対化は正確な学習よりも難しくはありません。^[5]

双対化アルゴリズムが与えられた場合、決定問題を解決することも簡単です。与えられたCNF式を双対化し、それが与えられたDNF式と等しいかどうかをテストします。したがって、この分野の研究は、この等価性の反対方向、つまり決定問題のサブルーチンが与えられた場合に正確な学習問題（または双対化問題）を解くことに焦点を当ててきました。^[4]

Bioch & Ibaraki (1995) は、決定サブルーチンを使用して正確な学習を解決するための次のアルゴリズムを概説しています。

• これまでに識別された主要な CNF 節と主要な DNF 節のセットを初期化し、最初は空にします。
• 次の手順を繰り返します。
  • 決定問題を使用して、現在のプライム CNF 節とプライム DNF 節のセットが双対であるかどうかをテストし、双対である場合はアルゴリズムを終了し、見つかった節を返します。
  • 関数値が既知の主要な DNF 節によって真に強制されることも、既知の主要な CNF 節によって偽に強制されることもない変数への真理値割り当てを構築します。この構築は、各ステップで決定問題を使用して、選択された真理値割り当てに制限される場合に CNF 節と DNF 節が非双対であるという特性を保持しながら、変数の値を 1 つずつ選択することによって実行できます。
  • この真理値割り当てで関数を評価します。これが真である場合、変数を 1 つずつ真から偽に変更して、関数が依然として真と評価される最小の真理値割り当てを見つけます。この最小の真理値割り当ては、まだ知られていない主要な DNF 節に対応します。これを既知の節のセットに追加します。
  • 対称的に、関数が false と評価された場合は、変数を 1 つずつ false から true に変更して、関数が依然として false と評価される最大の真理割り当てを見つけます。この最大の真理割り当ては、まだ知られていない主要な CNF 節に対応します。これを既知の節のセットに追加します。

アルゴリズムの外側のループの各反復では、決定問題への呼び出しを線形回数使用して強制されていない真理値の割り当てを見つけ、関数評価を線形回数使用して最小の真または最大の偽の関数値を見つけ、出力に1つの節を追加します。したがって、決定問題への呼び出しの合計数と関数評価の合計数は、合計出力サイズの多項式です。^[4]

マイケル・フレッドマンとレオニード・カチヤンによるこの問題の研究における中心的な結果は、単調双対化（その同等の形式のいずれか）は準多項式時間で解決できることである。^{[1] [6]}彼らのアルゴリズムは決定問題を直接解決するが、§ 異なる定式化の同値性で説明されているように、単調双対化問題の他の形式に変換することができる。あるいは、決定問題に対する答えが「いいえ」の場合、アルゴリズムは証拠、つまり入力式が関数値を決定できない真理値の割り当てを返すように変更することができる。その主なアイデアは、冗長な情報を削除し、問題の解決しやすい特定のケースを直接解決することにより、最初に決定問題のインスタンスを「クリーンアップ」することです。次に、残りのケースでは、慎重に選択された変数に分岐します。これは、同じアルゴリズムを 2 つの小さなサブ問題で再帰的に呼び出すことを意味します。1 つは、変数が true に設定されている制限された単調関数用で、もう 1 つは変数が false に設定されているものです。クリーニングステップでは、多くの節に属する変数の存在が保証され、再帰サブ問題のサイズが大幅に削減されます。^[1]

より詳細には、フレッドマンとカチヤンの2つのアルゴリズムのうち最初の遅いアルゴリズムは、以下のステップを実行します。^{[1] [6]}

• 指定された節のセットの中で最小ではない節を削除します。(つまり、削除された節は、同じタイプの別の節の変数のスーパーセットである変数のセットを使用します。)
• 2 つの節セット (決定問題の 1 つのバージョンでは CNF と DNF、または別のバージョンでは 2 つの双対関数を表すはずの CNF 節セット) が同じ変数セットをカバーしない場合は、それらが双対ではないことを返します。
• 異なる節セットの 2 つの節が互いに素な変数セットを使用している場合、それらが双対ではないことを返します。この場合、節は、両方と一致する任意の真理値割り当てに対して矛盾する関数値を暗示します。
• あるクラスのいずれかの節が、他のクラスの節の数よりも多くの変数を使用している場合、それらは双対ではないことを返します。この節が最小限である場合、そこから 1 つの変数を削除して同じ関数の有効な節を生成することはできませんが、他のクラスからの節がこれらの削除をブロックするのに十分な数ではありません。
• 各節について、関数値がその節によって決定される真理値割り当ての数を数えます。変数を含む問題における変数を含む節の場合、この数は です。両方のタイプのすべての節について加えられたこれらの数の合計が、存在する真理値割り当ての合計よりも少ない場合、2 つの節セットは双対ではないことを返します。つまり、少なくとも 1 つの真理値割り当てには、決定されない値が含まれている必要があります。${\displaystyle 2^{nk}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle 2^{n}}$
• どちらかの節セットが空の場合、または両方が 1 つの節のみで構成されている場合は、問題を特別なケースとして定数時間で処理します。
• 残りのケースでは、2 つの節セットの 1 つで大きな割合を占める変数が存在します。その変数に基づいて分岐します。より正確には、全節がある場合、(すべての真理値割り当てをカバーするために) 少なくとも 1 つの節に最大で 個の変数が含まれている必要があります。他の節セットの各節は、この短い節と空でない交差を持つ必要があります。そのため、短い節の変数の 1 つは、他の節セットの少なくとも一部に現れます。${\displaystyle m}$${\displaystyle \log_{2}m}$${\displaystyle 1/\log _{2}m}$

このアルゴリズムが多くの節に出現する変数で分岐する場合、これらの節は2つの再帰呼び出しの1つから除去されます。この事実を利用して、アルゴリズムの実行時間は指数関数で制限することができます。^{[1] [6]}${\displaystyle (\log n)^{3}}$

Fredman と Khachiyan の 2 番目のアルゴリズムは、全体的な構造は似ていますが、分岐変数が一方のセットの多くの節に出現し、もう一方のセットにはほとんど出現しない場合、2 つの再帰呼び出しのうち、分岐変数を設定することで節の数が大幅に減少する最初の呼び出しを選択します。その再帰呼び出しで矛盾が見つからない場合は、もう一方の分岐に対して 1 回の再帰呼び出しを実行する代わりに、その節の他のすべての変数が同じ方法で割り当てられた制限されたサブ問題に対して、分岐変数を含む各節に対して 1 回の呼び出しを実行します。実行時間は の指数関数です。^{[1] [6]}${\displaystyle (\log n)^{2}}$

単調双対化問題の多くの特殊なケースは、パラメータ化された複雑さの分析を通じて多項式時間で解けることが示されている。^[2]これには以下が含まれる。

• 各変数が限られた数の節に現れるCNFまたはDNF式の双対化^[7]、またはこのタイプの式を持つ単調関数の正確な学習^{[8] 。}
• 誘導されたサブハイパーグラフの平均次数が制限されている均一に疎なハイパーグラフの横断ハイパーグラフを構築する。 ^{[9]また、グラフ理論的概念である}木幅や退化の一般化が制限されているハイパーグラフの横断ハイパーグラフを構築する。^[10]
• 補集合（各ハイパーエッジを補完して得られるハイパーグラフ）の次数が低い横断ハイパーグラフを構築する。^[11]

単調双対化の応用例の1つは、複雑なシステムのモデルベース診断における障害検出と分離のためのグループテストです。システムの障害動作の観測値の集合から、それぞれがアクティブなコンポーネントのセットを持っている場合、この誤動作を引き起こしている障害コンポーネントは、このセットのファミリーの最小ヒットセットを形成する可能性が高いと推測できます。^{[2] [12]}

生化学工学では、ヒッティングセットの列挙は、システムから除去することでシステムのバランスを望ましい方向に調整する代謝反応のサブセットを識別するために使用されています。^{[2] [13] [14]}同様の方法は、他の生物学的相互作用ネットワークにも適用されており、たとえば、生物システムにおけるタンパク質相互作用を推測するために使用できるマイクロアレイ実験の設計に使用されています。 ^[2]

レクリエーション数学では、数独パズルの設計において、与えられた数字のグリッドを唯一の解とする手がかりのシステムを設計する問題は、最小ヒットセット問題として定式化できます。与えられたグリッドからの81の候補手がかりは、ヒットセットで選択される要素であり、ヒットされるセットは、各代替解を排除できる候補手がかりの集合です。したがって、最小ヒットセットの列挙を使用して、与えられた解を持つすべての手がかりシステムを検索できます。このアプローチは、16の手がかりのみで有効な数独パズルを設計することは不可能であるという計算証明の一部となっています。^{[2] [15]}