 Edmonds (1965a) first proposed that polynomial time complexity could be used as a positive criterion of feasibility – or, as he put it, possessing a “good algorithm” – in a paper in which he showed that a problem which might a priori be thought to be solvable only by brute force search (a generalization of \(\sc{PERFECT}\ \sc{MATCHING}\) from above) was decidable by a polynomial time algorithm.  Paralleling a similar study of brute force search in the Soviet Union, in a subsequent paper Edmonds (1965b) also provided an informal description of the complexity class \(\textbf{NP}\).  In particular, he characterized this class as containing those problems \(X\) for which there exists a “good characterization” – i.e. \(X\) is such that the membership of an instance \(x\) may be verified by using brute force search to find a certificate \(y\) of feasible size which certifies \(x\)’s membership in   \(X\).[9]