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?
Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper &quot;the equivalence problem for regular expressions with squaring requires exponential space&quot;. 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.