マトロイド
例えば、巡回セールスマン問題に対する独立性システムの独立性オラクルはつまり、与えられた辺集合がハミルトン閉路の部分集合であるかを判定するものであるが、グラフは完全グラフであるので、多項式時間で実行可能である。対して基拡張集合オラクルは与えられた辺集合からいくらか辺を削除することによってハミルトン閉路になるかということを判定しなくてはならない。それはつまりハミルトン閉路問題と等価であり、ハミルトン閉路問題はNP完全であるため難しいと言える。このように、独立性システムにおいて独立性オラクルと基拡張集合オラクルは必ずしも多項式等価ではない。
マトロイドにおいては独立性オラクル、基拡張集合オラクル、ランク関数を返すランクオラクル、閉包関数を返す閉包オラクル全て多項式等価である。しかし、与えられた部分集合が基かどうかを判定する基決定オラクルは独立性オラクルより弱いし、与えられた部分集合の最小元数の従属部分集合を返すオラクルは独立性オラクルより強い。
独立性システム (E, F) に対して、F を X ∩ B = ∅ {\displaystyle X\cap B=\emptyset } となる (E, F) の基 B が存在する X ⊆ E {\displaystyle X\subseteq E} の集合とする。このとき、(E, F) を (E,F) の双対 (dual) と定義する。
双対には次のような性質がある。
(E, F) = (E,F)
(E, F) が独立性システムならば、(E, F) は独立性システム
(E, F) はマトロイド ⟺ {\displaystyle \iff } (E, F) はマトロイド。
マトロイド (E, F) とその双対 (E, F) とし、それぞれのランク関数を r, r とすると、r は任意の X ⊆ E に対して r ∗ ( X ) = | X | + r ( E ∖ X ) − r ( E ) {\displaystyle r^{*}(X)=|X|+r(E{\setminus }X)-r(E)} である。
2つの独立性システム (E, F1), (E, F2) とするとき、(E, F1 ∩ F2) を2つの独立性システムの交差 (intersection) と定義する。有限個の独立性システムの交差も同様に定義でき、交差もまた独立性システムとなる。任意の独立性システム (E, F) は、有限個のマトロイドの交差で表せる。さらに、p 個のマトロイドの交差ならば、q(E, F) ≧ 1/p。
例えば2部グラフのマッチング問題の場合、Eを辺集合、Fをマッチング集合とすれば、2部グラフであるから点集合は A ∪ B と書ける。F1 を任意の点 a ∈ A に繋がる辺は高々1本であるという条件とするならば (E, F1) はマトロイドであり、同様に F2 を任意の点 b ∈ B に繋がる辺は高々1本であるという条件とするならば (E, F2) もマトロイドである。F = F1 ∩ F2 なので、(E, F) は2つのマトロイド (E, F1), (E, F2) の交差である。
下方ランク (lower rank) 関数 ρ ( X ) {\displaystyle \rho (X)} を X {\displaystyle X} に含まれる基の最小元数とする。つまり、
ρ ( X ) := min { | Y | : Y ⊆ X , Y ∈ F {\displaystyle \rho (X):=\min\{|Y|:Y\subseteq X,Y\in F} かつ ∀ x ∈ X ∖ Y {\displaystyle \forall {x}\in X\setminus Y} に対し Y ∪ { x } ∉ F } {\displaystyle Y\cup \{x\}\not \in F\}}
と定義する。すると、ランク商 (rank quotient) は次のように定義される。