  Given a matroid $M=(E,{\cal I})$, and a total ordering over the elements $E$,
a broken circuit is a circuit where the smallest element is removed and an NBC
independent set is an independent set in ${\cal I}$ with no broken circuit. The
set of NBC independent sets of any matroid $M$ define a simplicial complex
called the broken circuit complex which has been the subject of intense study
in combinatorics. Recently, Adiprasito, Huh and Katz showed that the face of
numbers of any broken circuit complex form a log-concave sequence, proving a
long-standing conjecture of Rota.
  We study counting and optimization problems on NBC bases of a generic
matroid. We find several fundamental differences with the independent set
complex: for example, we show that it is NP-hard to find the max-weight NBC
base of a matroid or that the convex hull of NBC bases of a matroid has edges
of arbitrary large length. We also give evidence that the natural down-up walk
on the space of NBC bases of a matroid may not mix rapidly by showing that for
some family of matroids it is NP-hard to count the number of NBC bases after
certain conditionings.

Computational Complexity;Data Structures and Algorithms;Combinatorics