I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing.
Linear Programming is $\mathsf{P}$-complete, which means that every problem in $\mathsf{P}$ can be reduced to it using an $\mathsf{NC}$ reduction. (See the wiki for some nice background)
However, it has been shown that the perfect matching polytope has exponentially many facets (see this recent STOC paper for example. This shows it even has exponential extension complexity---i.e. even using extra dimensions we require an exponential number of inequalities).
However, the classic Blossom Algorithm can find a perfect matching in polynomial time--determining if a graph has a perfect matching is in $\mathsf{P}$.
This seems like a conflict to me: we can reduce the perfect matching problem to Linear Programming, but its polytope must be exponentially large. What am I mising? Is there processing during the reduction that avoids using the entire matching polytope?