<p>Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper <a href="https://doi.org/10.1109/SWAT.1972.29" rel="nofollow noreferrer">&quot;the equivalence problem for regular expressions with squaring requires exponential space&quot;</a>. The class <span class="math-container">$\Pi_1^P$</span> in there is of course coNP. Stockmeyer wrote a <a href="https://doi.org/10.1016/0304-3975(76)90061-X" rel="nofollow noreferrer">full paper</a> on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.</p>

CC BY-SA 4.0
2020-08-07T15:43:24.323Z
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
CC BY-SA 4.0
2020-08-07T18:44:25.090Z
Many thanks for the catches! I'll update my answer accordingly
Hermann Gruber
CC BY-SA 4.0
2020-08-03T17:02:21.007Z
2020-08-07T20:30:01.953Z
2020-08-07T20:30:01.953Z
Hermann Gruber
<p>My best finding is Pratt's 1975 <a href="https://pdfs.semanticscholar.org/533b/a306dbd8e4f483372d177d898ef4963c9a02.pdf" rel="noreferrer">article</a>. Is there any earlier mention of co-NP?</p>

CC BY-SA 4.0
2020-08-02T18:49:40.117Z
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 
CC BY-SA 4.0
2024-09-19T18:14:22.630Z
It seems Meyer & Stockmeyer were first, but just to point out that Cook & Reckhow STOC 1974 also talk about the complements of NP languages (they show NP is closed under complement iff a "super proof system" exists, and various related results), though they do not explicitly use the name "coNP".
Joshua Grochow
<np><ho.history-overview>
When was co-NP introduced for the first time?
Jérôme Verstrynge
# When was co-NP introduced for the first time?

(Asked by: username_0 on 2020-08-02)

My best finding is Pratt's 1975 [article](https://pdfs.semanticscholar.org/533b/a306dbd8e4f483372d177d898ef4963c9a02.pdf). Is there any earlier mention of co-NP?

**Tags:** np, ho.history-overview
> **Comments:**
> **username_1**: 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.  
> **username_2**: It seems Meyer & Stockmeyer were first, but just to point out that Cook & Reckhow STOC 1974 also talk about the complements of NP languages (they show NP is closed under complement iff a "super proof system" exists, and various related results), though they do not explicitly use the name "coNP".  

---

## 1 answers

### Answer by username_3 on 2020-08-03. Score: 14 | Accepted answer

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"](https://doi.org/10.1109/SWAT.1972.29). The class $\Pi\_1^P$ in there is of course coNP. Stockmeyer wrote a [full paper](https://doi.org/10.1016/0304-3975(76)90061-X) on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.

> **Comments:**
> **username_0**: 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.  
> **username_3**: Many thanks for the catches! I'll update my answer accordingly  

---

