A perfect matching in an undirected graph $G=(V,E)$ is a set of vertex
disjoint edges from $E$ that include all vertices in $V$. The perfect matching
problem is to decide if $G$ has such a matching. Recently Rothvoß proved
the striking result that the Edmonds' matching polytope has exponential
extension complexity. Here for each $n=|V|$ we describe a perfect matching
polytope that is different from Edmonds' polytope and define a weaker notion of
extended formulation. We show that the new polytope has a weak extended
formulation (WEF) $Q$ of polynomial size. For each graph $G$ with $n$ vertices
we can readily construct an objective function so that solving the resulting
linear program over $Q$ decides whether or not $G$ has a perfect matching. The
construction is uniform in the sense that, for each $n$, a single polytope is
defined for the class of all graphs with $n$ nodes. The method extends to solve
poly time optimization problems, such as the weighted matching problem. In this
case a logarithmic (in the weight of the optimum solution) number of
optimizations are made over the constructed WEF.
The method described in the paper involves construction of a compiler that
converts an algorithm given in a prescribed pseudocode into a polytope. It can
therefore be used to construct a polytope for any decision problem in {\bf P}
which can be solved by a given algorithm. Compared with earlier results of
Dobkin-Lipton-Reiss and Valiant our method allows the construction of explicit
linear programs directly from algorithms written for a standard register model,
without intermediate transformations. We apply our results to obtain polynomial
upper bounds on the non-negative rank of certain slack matrices related to
membership testing of languages in {\bf P/Poly}.