Jump to content

Talk:Matroid oracle

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is the current revision of this page, as edited by Cewbot (talk | contribs) at 23:43, 5 February 2024 (Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Maths rating}}. Remove 1 deprecated parameter: field.). The present address (URL) is a permanent link to this version.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Matroid_oracle&oldid=1203921170"