Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Matroid oracle
open-in-new
<p>In mathematics and computer science, a matroid oracle is a <a href="/facts/Subroutine/9vFJrg0A">subroutine</a> through which an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> may access a <a href="/facts/Matroid/5bLcGlRF">matroid</a>, an abstract combinatorial structure that can be used to describe the <a href="/facts/Linear_independence/8JrHfIIa">linear dependencies</a> between vectors in a <a href="/facts/Vector_space/M1pxMLx2">vector space</a> or the <a href="/facts/Spanning_tree/qQPN9taR">spanning trees</a> of a <a href="/facts/Undirected_graph/kw3eIBUe">graph</a>, among other applications. </p><p>The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power. </p><p>Many <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. For instance, given an independence oracle for any matroid, it is possible to find the minimum weight basis of the matroid by applying a <a href="/facts/Greedy_algorithm/alfsekco">greedy algorithm</a> that adds elements to the basis in sorted order by weight, using the independence oracle to test whether each element can be added. </p><p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, the <a href="/facts/Oracle_machine/6ScMuvvY">oracle model</a> has led to unconditional <a href="/facts/Lower_bound/YJje9oC2">lower bounds</a> proving that certain matroid problems cannot be solved in polynomial time, without invoking unproved assumptions such as the assumption that <a href="/facts/P_versus_NP_problem/xoC7Ruda">P ≠ NP</a>. Problems that have been shown to be hard in this way include testing whether a matroid is <a href="/facts/Binary_matroid/4Iw9nDrM">binary</a> or <a href="/facts/Uniform_matroid/nVAV66la">uniform</a>, or testing whether it contains certain fixed <a href="/facts/Matroid_minor/nrEV2Sn2">minors</a>. </p>