マトロイドオラクル

数学とコンピュータサイエンスにおいて、マトロイドオラクルとは、アルゴリズムがマトロイドにアクセスするためのサブルーチンです。マトロイドは、ベクトル空間内のベクトル間の線形依存関係やグラフの全域木などを記述するために使用できる抽象的な組み合わせ構造です。

このタイプのオラクルの中で最も一般的に使用されるのは独立性オラクルであり、マトロイド要素の集合が独立しているかどうかをテストするサブルーチンです。他のいくつかのタイプのオラクルも使用されており、その中には独立性オラクルよりも弱いもの、強いもの、計算能力が同等のものなどがあります。^[1]

マトロイドの計算を行うアルゴリズムの多くは、オラクルを入力として受け取るように設計されており、さまざまなマトロイドの種類を変更せずに効率的に実行でき、使用しているマトロイドの種類に関する追加の仮定も必要ありません。たとえば、任意のマトロイドの独立オラクルが与えられた場合、独立オラクルを使用して各要素を追加できるかどうかをテストし、重み順にソートされた順序で要素を基底に追加する貪欲アルゴリズムを適用することで、マトロイドの最小重み基底を見つけることができます。 ^[2]

計算複雑性理論では、オラクルモデルは、P≠NPなどの証明されていない仮定を使わずに、特定のマトロイド問題が多項式時間で解くことができないことを証明する無条件の下限値を導いた。このようにして困難であることが示されている問題には、マトロイドがバイナリかユニフォームかをテストすることや、マトロイドに特定の固定マイナーが含まれているかどうかをテストすることなどがある。^[3]

一部の著者は、マトロイドのすべての独立集合またはすべての基底集合を明示的にリストするマトロイドのコンピュータ表現を実験してきましたが、^[4]これらの表現は簡潔ではありません。要素を持つマトロイドは、空間を指数的に取る表現に拡張される可能性があります。実際、要素上の異なるマトロイドの数は、 ${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle n}$

${\displaystyle 2^{2^{n}n^{-3/2+o(1)}}}$^[5]

そこから、あらゆる可能なマトロイドを扱うことができる明示的な表現は、必然的に指数空間を使用することがわかる。^[6]

代わりに、異なるタイプのマトロイドは、それらが定義されている他の構造からより効率的に表現できます。たとえば、 2 つの数値パラメータからの一様マトロイド、グラフからグラフィックマトロイド、双円マトロイド、ガモイド、行列から線形マトロイドなどです。ただし、任意のマトロイドに対して計算を実行するアルゴリズムでは、これらのマトロイド クラスごとに再設計するのではなく、引数にアクセスするための統一された方法が必要です。オラクル モデルは、アルゴリズムに必要なアクセスの種類をコード化して分類する便利な方法を提供します。

Rado (1942) 以来、「独立関数」または「-関数」は、マトロイドを公理化する多くの同等の方法の 1 つとして研究されてきました。独立関数は、マトロイド要素の集合が独立であるか従属しているかに応じて、その集合を数値にマッピングします。つまり、独立集合の族の指標関数であり、本質的には独立オラクルと同じです。^[7]${\displaystyle \scriptstyle I}$${\displaystyle \scriptstyle 1}$${\displaystyle \scriptstyle 0}$

マトロイドオラクルも、マトロイドに関する最も初期のアルゴリズム研究の一部でした。そのため、マトロイド分割問題を研究する中で、Edmonds (1965) は、与えられたマトロイドへのアクセスは、独立集合と要素 を入力として受け取り、内の回路(存在する場合は を含み、必ず一意)を返すか、そのような回路は存在しないと判断するサブルーチンを介して行われるものと想定しました。Edmonds (1971) は、与えられた集合が独立であるかどうかをテストするサブルーチン (つまり、より現代的な用語では、独立性オラクル) を使用し、それが提供する情報は、多項式時間で最小の重み基底を見つけるのに十分であることを観察しました。 ${\displaystyle \scriptstyle I}$${\displaystyle \scriptstyle x}$${\displaystyle \scriptstyle I\cup \{x\}}$${\displaystyle \scriptstyle x}$

Korte & Hausmann (1978) と Hausmann & Korte (1978) の研究を皮切りに、研究者たちはマトロイドや関連構造のアルゴリズムの下限を証明するという観点からオラクルの研究を始めました。Hausmann と Korte によるこの 2 つの論文はどちらも、最大濃度の独立集合を見つける問題に関するものでした。これはマトロイドでは簡単ですが、独立オラクルによって表現されるより一般的な独立システムでは近似または正確な計算が困難です (彼らが示したように) 。この研究は、1970 年代後半から 1980 年代前半にかけて、マトロイドの問題に対する同様の困難性の結果を示す論文^[8]や、さまざまな種類のマトロイドオラクルの能力を比較する論文の急増のきっかけとなりました^{[9] 。}

それ以来、独立オラクルはマトロイドアルゴリズムのほとんどの研究の標準となっています。^{[10]また、下限値の研究や[11]}異なるタイプのオラクルの比較も継続して行われています。 ^[12]

以下のタイプのマトロイドオラクルが検討されています。

• 独立性オラクルでは、マトロイド要素の集合を入力として受け取り、ブール値 を出力として返します。指定された集合が独立している場合は true、そうでない場合は false です。^[13]グラフィックマトロイド、横断マトロイド、ガモイド、線形マトロイド、およびこれらから直接和などの標準的な演算によって形成されたマトロイドに対して、マトロイドが定義された基礎構造に基づいて簡単に実装できます。^[3]
• 基底オラクルはマトロイド要素の集合を入力として受け取り、与えられた集合が基底であれば真、そうでなければ偽のブール値を出力として返します。^[9]
• 回路オラクルはマトロイド要素の集合を入力として受け取り、与えられた集合が回路であれば真、そうでなければ偽のブール値を出力として返します。^[9]
• エドモンズ (1965) の回路検索オラクルでは、独立集合と追加要素を入力として受け取り、それらの和集合が独立であると判断するか、和集合内の回路を見つけてそれを返します。
• ランクオラクルはマトロイド要素の集合を入力として受け取り、与えられた集合のランクを数値として出力します。 ^[9]
• 3種類の閉包オラクルが検討されている。1つは与えられた要素が与えられた集合の閉包に属するかどうかをテストするもの、2つ目は集合の閉包を返すもの、3つ目は与えられた集合が閉じているかどうかをテストするもの。^[9]
• スパニングオラクルはマトロイド要素の集合を入力として受け取り、ブール値を出力として返します。与えられた集合がスパニング（つまり基底を含み、マトロイド全体と同じランクを持つ）の場合はtrue、それ以外の場合はfalseです。^[14]
• ガースオラクルはマトロイド要素の集合を入力として受け取り、その集合内の最小回路のサイズ（または与えられた集合が独立している場合）を数値として出力します。 ^[14]${\displaystyle \scriptstyle +\infty}$
• マトロイドの固定要素のポートオラクルは、マトロイド要素の集合を入力として受け取り、ブール値を出力として返します。指定された集合にそれを含む回路が含まれている場合はtrue 、そうでない場合はfalseとなります。^[15]${\displaystyle \scriptstyle x}$${\displaystyle \scriptstyle x}$

多くの種類のオラクルが知られていますが、それらの多くは計算能力において同等であるため、どれを使用するかの選択は単純化できます。オラクルへの任意の呼び出しが、オラクル のみを使用してマトロイドにアクセスし、マトロイドの要素の数で測定された多項式時間で実行されるアルゴリズムによってシミュレートできる場合、オラクル は別のオラクル に多項式的に還元可能であると言われます。複雑性理論的には、これはチューリング還元 です。2つのオラクルが互いに多項式的に還元可能である場合、それらのオラクル は多項式的に同等であると言われます。と が多項式的に同等である場合、オラクル を使用したマトロイド問題の多項式時間アルゴリズムの存在または非存在を証明するすべての結果は、オラクル についても同じことを証明します。 ${\displaystyle \scriptstyle X}$${\displaystyle \scriptstyle Y}$${\displaystyle \scriptstyle X}$${\displaystyle \scriptstyle Y}$${\displaystyle \scriptstyle X}$${\displaystyle \scriptstyle Y}$${\displaystyle \scriptstyle X}$${\displaystyle \scriptstyle Y}$

たとえば、独立性オラクルは、エドモンズ (1965) の回路探索オラクルと多項式的に同等です。回路探索オラクルが利用できる場合、オラクルを最大で呼び出してセットの独立性をテストできます。つまり、空のセットから始めて、指定されたセットの要素を一度に 1 つずつ追加し、回路探索オラクルを使用して、各追加によって、これまでに構築されたセットの独立性が維持されるかどうかをテストします。逆に、独立性オラクルが利用できる場合、オラクルを最大で呼び出して、各要素 について が独立かどうかをテストし、答えが「いいえ」である要素を返すことで、セット内の回路を見つけることができます。独立性オラクルは、ランクオラクル、スパニングオラクル、最初の 2 種類のクロージャオラクル、およびポートオラクルとも多項式的に同等です。^[1]${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle I\cup \{x\}}$${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle y\in I}$${\displaystyle \scriptstyle I\setminus \{y\}\cup \{x\}}$

基底オラクル、回路オラクル、および与えられた集合が閉じているかどうかをテストするオラクルはすべて独立オラクルよりも弱い。これらは独立オラクルを使用してマトロイドにアクセスするアルゴリズムによって多項式時間でシミュレートできるが、その逆はできない。さらに、これら3つのオラクルはいずれも多項式時間内で互いをシミュレートできない。同じ意味で、ガースオラクルは独立オラクルよりも強い。^[9]

多項式時間のチューリング還元だけでなく、他の種類の還元可能性も検討されてきました。特に、Karp、Upfal、Wigderson (1988) は、並列アルゴリズムでは、ランクオラクルと独立オラクルの計算能力に大きな違いがあることを示しました。ランクオラクルは、マトロイド要素のソート順のプレフィックスを同時に照会することで、最小重み基底の構築を可能にします。要素が最適な基底に属するのは、そのプレフィックスのランクが前のプレフィックスのランクと異なる場合のみです。対照的に、独立オラクルで最小基底を見つけるのははるかに遅くなります。これは時間ステップで決定論的に解決でき、ランダム化並列アルゴリズムの場合でも の下限があります。${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle O({\sqrt {n}})}$${\displaystyle \scriptstyle \Omega ((n/\log n)^{1/3})}$

マトロイドに関する多くの問題は、どのようなマトロイドが与えられたかという追加の仮定を必要とせず、独立オラクルまたは同等のパワーを持つ別のオラクルを通じてのみマトロイドにアクセスするアルゴリズムによって、多項式時間で解決できることが知られています。これらの多項式で解決可能な問題には次のものが含まれます。

• 貪欲アルゴリズムを使用して、重み付きマトロイドの最小または最大の重み基底を見つける。^[2]
• マトロイドの要素を最小数の独立集合に分割し、与えられた2つのマトロイドにおいて同時に独立な最大の集合を求める。後者の問題はマトロイド交差と呼ばれ、両方の問題の解は互いに密接に関連している。^[16]
• マトロイドが（Tutte 1966の意味で）連結であるかどうかをテストする。^[17]${\displaystyle \scriptstyle k}$${\displaystyle \scriptstyle k\leq 3}$
• 与えられたマトロイドがグラフィック^[18]か正則^[19]かをテストする。
• 与えられたマトロイドの分解を見つけること。マトロイドとは、その和集合がマトロイドであり、そのシーケンス内の前の回路がすべて縮約された後も各回路が回路のままである回路のシーケンスのことである。このような分解は、選択されたマトロイド要素がすべての回路に属するという追加の特性とともに見つけることもできる。^[15]
• 与えられたマトロイドの分岐幅が一定定数以下の場合に、そのマトロイドの分岐分解を求める。 ^[20]
• マトロイドの基底、平面、回路のすべてを出力セットごとに多項式時間でリストする。^[21]
• 要素とランクを持つマトロイドの基底の数を、完全な多項式時間ランダム近似スキームで近似する。ただし、基底の数は要素セットの数の多項式因数以内であるという追加の仮定を置く。^[22]${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle r}$${\displaystyle \scriptstyle r}$

多くのマトロイド問題では、独立オラクルでは問題を多項式時間で解くのに十分なパワーがないことを示すことができます。これらの証明の主なアイデアは、問題の答えが異なり、アルゴリズムが区別するのが難しい2 つのマトロイドとを見つけることです。特に、が高度な対称性を持ち、少数のクエリに対する答えのみが と異なる場合、アルゴリズムが 型の入力と の対称性の 1 つを使用して を並べ替えることによって形成された入力を確実に区別するには、非常に多くのクエリが必要になる場合があります。^[3]${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$

このアプローチの簡単な例を使って、マトロイドが均一 であるかどうかをテストするのが難しいことを示すことができます。説明を簡単にするために、 を偶数、 を均一マトロイド、 をの- 要素基底セットの 1 つを独立ではなく従属にすることでから形成されたマトロイドとします。アルゴリズムが入力が均一であるかどうかを正しくテストするには、のあらゆる可能な順列を区別できなければなりません。しかし、決定論的アルゴリズムがこれを行うには、要素の - 要素サブセットの 1 つすべてをテストする必要があります。1 つのセットを見逃すと、 を従属させるセットとして同じセットを選択したオラクルによって騙される可能性があります。したがって、マトロイドが均一であるかどうかをテストするには、 ${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle U{}_{n}^{n/2}}$${\displaystyle \scriptstyle M'}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle n/2}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$${\displaystyle \scriptstyle n/2}$

${\displaystyle {\binom {n}{n/2}}=\Omega \left({\frac {2^{n}}{\sqrt {n}}}\right)}$

独立クエリは多項式よりもはるかに高い。ランダム化アルゴリズムであっても、これら2つのマトロイドを確実に区別するためには、ほぼ同じ数のクエリを実行する必要がある。^[23]

ジェンセンとコルテ（1982）は、このアプローチを形式化して、同じ要素の集合上に2つのマトロイドが存在するが、問題の答えが異なる場合、それらの要素上で与えられた問題を正しく解くアルゴリズムは、少なくとも ${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$

${\displaystyle {\frac {|\operatorname {aut} (M)|}{\sum _{i}|\operatorname {fix} (M,Q_{i})|}}}$

クエリ、ここで はの自己同型群、は からまでの独立性が異なる集合の族、 はそれ自身に写像される自己同型の部分群を表します。たとえば、一様マトロイドの自己同型群は、サイズ の対称群であり、一様マトロイドをテストする問題では、 より指数係数だけ小さい を持つ集合は 1 つしかありませんでした。^[24]${\displaystyle \scriptstyle \operatorname {aut} (M)}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle Q_{i}}$${\displaystyle \scriptstyle M}$${\displaystyle \scriptstyle M'}$${\displaystyle \scriptstyle \operatorname {fix} (M,Q_{i})}$${\displaystyle \scriptstyle Q_{i}}$${\displaystyle \scriptstyle n!}$${\displaystyle \scriptstyle Q_{i}}$${\displaystyle \scriptstyle |\operatorname {fix} (M,Q_{i})|=(n/2)!^{2}}$${\displaystyle \scriptstyle n!}$

マトロイド オラクル アルゴリズムが多項式時間で計算することが不可能であることが証明されている問題には、次のものがあります。

• 与えられたマトロイドが均一かどうかをテストする。^[23]
• 与えられたマトロイドに固定のマトロイドがマイナーとして含まれているかどうかをテストする。ただし、 が均一でランクまたはコランクが最大で 1 である特殊な場合は除く。より一般的には、 がマトロイドの固定された有限集合であり、 に均一なマトロイドが存在しない場合、与えられたマトロイドに のマトロイドの 1 つ以上がマイナーとして含まれているかどうかを多項式時間でテストすることは不可能である。 ^[25]${\displaystyle \scriptstyle H}$${\displaystyle \scriptstyle H}$${\displaystyle \scriptstyle {\mathcal {H}}}$${\displaystyle \scriptstyle {\mathcal {H}}}$${\displaystyle \scriptstyle {\mathcal {H}}}$
• 与えられたマトロイドがバイナリであるか、特定の固定体上で表現可能か、あるいは表現可能な体が存在するかどうかをテストする。^[26]
• マトロイドマッチング問題を解く。入力はグラフとその頂点上のマトロイドであり、目標はマッチングされた頂点が独立した集合を形成するという制約の下で、グラフ内で可能な限り大きなマッチングを見つけることである。^[27]
• 与えられたマトロイドが自己双対、横断的、二部的、オイラー的、または有向的であるかどうかをテストする。^[3]
• 与えられたマトロイドの内周（最小回路の大きさ）、最大回路の大きさ、回路の数、基底の数、フラットの数、最大ランクフラットの数、最大フラットの大きさ、Tutte多項式、または接続性を計算する。^[3]

要素マトロイドのすべての特性の集合の中で、指数時間でテストできない特性の割合は、極限ではゼロになり、無限大になる。^[6]${\displaystyle \scriptstyle n}$${\displaystyle \scriptstyle n}$

• ブラックボックス群、群論の神託のようなモデル
• 暗黙のグラフ、グラフアルゴリズムのためのオラクルのようなモデル