  The decomposition theory of matroids initiated by Paul Seymour in the 1980's
has had an enormous impact on research in matroid theory. This theory, when
applied to matrices over the binary field, yields a powerful decomposition
theory for binary linear codes. In this paper, we give an overview of this code
decomposition theory, and discuss some of its implications in the context of
the recently discovered formulation of maximum-likelihood (ML) decoding of a
binary linear code over a discrete memoryless channel as a linear programming
problem. We translate matroid-theoretic results of Gr\"otschel and Truemper
from the combinatorial optimization literature to give examples of non-trivial
families of codes for which the ML decoding problem can be solved in time
polynomial in the length of the code. One such family is that consisting of
codes $C$ for which the codeword polytope is identical to the Koetter-Vontobel
fundamental polytope derived from the entire dual code $C^\perp$. However, we
also show that such families of codes are not good in a coding-theoretic sense
-- either their dimension or their minimum distance must grow sub-linearly with
codelength. As a consequence, we have that decoding by linear programming, when
applied to good codes, cannot avoid failing occasionally due to the presence of
pseudocodewords.
