We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, in a spanning tree matroid, the minimum hitting set should be a minimum cut. Thanks.


Crossposted at [CSTheory](https://cstheory.stackexchange.com/questions/11498/min-hitting-set-of-every-base-of-a-matroid). 



A minimum set hitting every base of a matroid
The problem is hard in general. Note that a minimal set that intersects every base of a matroid $M$ is a dependent set in the dual matroid $M^{\*}$. Such sets are called *cocircuits*. So, you are looking for the shortest cocircuit of a matroid. 


The shortest cocircuit problem (equivalently shortest circuit problem) is NP-complete in general (even for binary matroids). See this Matroid Union [post](http://matroidunion.org/?p=1106) for more information on finding shortest circuits in binary matroids. 


