マトロイド
最良選択貪欲法は、 c ( e ) {\displaystyle c(e)} の大きい順に e ∈ E {\displaystyle e\in E} を暫定解に追加できるならば追加し追加できない場合は次の要素に移ることを繰り返すアルゴリズムである。つまり、
c ( e 1 ) ≥ c ( e 2 ) ≥ ⋯ ≥ c ( e n ) {\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})} となるように E = { e 1 , e 2 , ⋯ , e n } {\displaystyle E=\{e_{1},e_{2},\cdots ,e_{n}\}} をソートする。
E a n s ← ∅ {\displaystyle E_{ans}\leftarrow \emptyset }
For i = 1 to n : E a n s ∪ { e i } ∈ F {\displaystyle E_{ans}\cup \{e_{i}\}\in F} ならば E a n s ← E a n s ∪ { e i } {\displaystyle E_{ans}\leftarrow E_{ans}\cup \{e_{i}\}}
組合せ最適化問題において F は明示的に与えられることはまずない。F を列挙しようとすることは無謀であるので、現実には E とコスト関数cのみが与えられる。最良選択貪欲法を実行するには、さらに独立性オラクルを必要となる。独立性オラクルとは、X ⊆ E が与えられたとき X ∈ F であるかどうかを判定するオラクルである。これがないと最良選択貪欲法の3番目のステップは実行できない。同様に最悪棄却貪欲法を実行するためには X ⊆ E が与えられたとき X が基を含むかを判定する基拡張集合オラクルを必要とする。
では、独立性オラクルか基拡張集合オラクルどちらか一方が与えられたとき、そのオラクルを使ってもう一方を多項式時間で実行可能(多項式等価)だろうか。