and an impractical algorithm (in modern terms, a tractable problem or intractable problem). Today, problems solvable in polynomial time are called the complexity class PTIME, or simply P. Edmonds's paper “Maximum Matching and a Polyhedron with 0-1 Vertices” along with his previous work gave astonishing polynomial-time algorithms for the construction of maximum matchings. Most notably, these papers demonstrated how a good characterization of the polyhedron associated with a combinatorial optimization problem could lead, via the duality theory of linear programming, to the construction of an efficient algorithm for the solution of that problem. Additional landmark work of Edmonds is in the area of matroids. He found a polyhedral description for all spanning trees of a graph, and more generally for all independent sets of a matroid. Building on this, as a novel application of linear programming to discrete mathematics, he proved the matroid intersection theorem, a very general combinatorial min-max theorem which, in modern terms, showed that the matroid intersection problem lay in both NP and co-NP. Edmonds is well known for his theorems on max-weight branching algorithms and packing edge-disjoint branchings and his work with Richard Karp on faster flow algorithms. The Edmonds–Gallai decomposition theorem describes finite graphs from the point of view of matchings. He introduced polymatroids, submodular flows with Richard Giles, and the terms clutter and blocker in the study of hypergraphs. A recurring theme in his work is to seek algorithms whose time complexity is polynomially bounded by their input size and bit-complexity. Career From 1969 on, with the exception of 1991–1993, he held a faculty position at the Department of Combinatorics and Optimization at the University of Waterloo's Faculty of Mathematics where his research encompassed combinatorial optimization problems and associated polyhedra. He supervised the doctoral work of a dozen students in this time. From 1991 to 1993, he was involved in a dispute ("the Edmonds affair") with the University of Waterloo, wherein the university claimed that a letter submitted constituted a letter of resignation, which Edmonds denied. The conflict was resolved in 1993, and he returned to the university. Edmonds retired from the University of Waterloo in 1999. Awards and honors Edmonds was the 1985 recipient of the John von Neumann Theory Prize. In 2001 his paper, "Path, Trees and Flowers" was honoured as an Outstanding Publication by the National Institute of Standards and Technology in their celebratory edition of A Century of Excellence in