Find a perfect matching in a bipartite graph with an odd number of red edges. The problem is solvable in polynomial time. It is easy.
Now describe the set of all solutions as a polytope — the convex hull of all feasible matchings in some space of edge variables. This should also be easy. For most polynomial-time combinatorial problems, the polytope has a compact description: a polynomial number of inequalities with small, simple coefficients. The matching polytope itself, famously, is described by constraints with coefficients in {0, 1}.
Nägele et al. prove that the odd-red perfect matching polytope requires constraints with large and diverse coefficients. No relaxation using {0, ±1} coefficients — the standard toolkit of polyhedral combinatorics — can describe it exactly. A previously proposed exponential-size relaxation is shown to be inexact and hard to separate over.
The problem is easy. Its geometry is hard. Solving instances and describing the solution space are different kinds of difficulty. Polynomial-time solvability implies efficient algorithms but does not imply efficient geometric descriptions. The polytope inherits some complexity that the algorithm avoids.
The gap between computational tractability and geometric tractability is not an anomaly. It is a structural feature: the convex hull can be complicated even when optimization over it is simple, because the hull must represent all solutions simultaneously while the algorithm only needs to find one.