My best finding is Pratt's 1975 article. Is there any earlier mention of co-NP?
$\begingroup$
$\endgroup$
1
-
8$\begingroup$ 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. $\endgroup$– Peter ShorAug 2, 2020 at 18:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Aug 3, 2020 at 17:02
-
1$\begingroup$ 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. $\endgroup$ Aug 7, 2020 at 15:43
-
1$\begingroup$ Many thanks for the catches! I'll update my answer accordingly $\endgroup$ Aug 7, 2020 at 18:44