11
$\begingroup$

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

$\endgroup$
  • 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 Shor Aug 2 at 18:49
14
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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$ – Jérôme Verstrynge Aug 7 at 15:43
  • 1
    $\begingroup$ Many thanks for the catches! I'll update my answer accordingly $\endgroup$ – Hermann Gruber Aug 7 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.