Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this talk, we discuss known approaches and their limitations. In particular, we show that there is no sub-exponential-sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential-sized linear program to describe the convex hull of perfect matchings with an odd number of red edges. To prove our result, we devise an exponential set of valid constraints that we believe are interesting in their own right. In particular, we leave as an open problem whether they define the convex hull of perfect matchings with an odd number of red edges. This is joint work with Xinrui Jia and Weiqiang Yuan