Talk:Matroid oracle

Latest comment: 1 year ago by Erel Segal in topic Relative power of different oracles

Relative power of different oracles

edit

"If a circuit-finding oracle is available, a set may be tested for independence using at most n calls to the oracle by starting from an empty set, adding elements of the given set one element at a time, and using the circuit-finding oracle to test whether each addition preserves the independence of the set that has been constructed so far"

I do not understand why we need n calls to the oracle, and not a single call? If the single call finds a circuit, then the set is not independent; otherwise, it is independent. Erel Segal (talk) 12:00, 28 November 2022 (UTC)Reply