# When was co-NP introduced for the first time?

My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?

• If you read Jack Edmond's 1965 article "Minimum partition of a matroid into independent subsets" (referenced in Pratt's article), it's clear he understood NP and co-NP, but he used the terminology "good characterization" instead. – Peter Shor Aug 2 '20 at 18:49

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space". The class $$\Pi_1^P$$ in there is of course coNP. Stockmeyer wrote a full paper on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.
• I think you meant their 1972 "The equivalence problem for regular expressions with squaring requires exponential space" paper (DOI: 10.1109/SWAT.1972.29), not "word problems requiring exponential time (preliminary report)". $\Pi_1^P$ is defined on page 28. Moreover, Stockmeyer confirms this initial reference in his 1977 "The Polynomial Hierarchy" paper at p.5. – Jérôme Verstrynge Aug 7 '20 at 15:43