Talk:Matroid oracle
Add topicLatest comment: 3 years ago by Erel Segal in topic Relative power of different oracles
 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
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)