<p>Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979).  This is very clear. As for the terminology, strictly speaking, Valiant does not use the term "counting complexity" in this paper. Instead, he speaks of "counting problems" in several places. In any case, it is probably hard to tell who coined these terms first, but this is probably also not very important. </p>

<p>What remains important is the fact that the complexity class $\mathsf{PP}$ (which, intuitively, is the decision-theoretic variant of $\mathsf{\#P}$) had already been introduced in 1974, by Gill's seminal paper "Computational complexity of probabilistic Turing machines". In this sense, Valiant was very much influenced by Gill's work. In fact, Valiant cites Gill's paper and loosely tells that #P is essentially equivalent to $\mathsf{PP}$ (which is not meant in the strict, formal sense). </p>

CC BY-SA 3.0
2017-04-14T01:33:56.190Z
2017-04-14T01:33:56.190Z
Heyheyhey
<p>Was #P first introduced in <a href="https://sites.math.washington.edu/~billey/colombia/references/valiant.permanent.1979pdf.pdf" rel="noreferrer">[1]</a>?</p>

<blockquote>
  <p>[1] Valiant, Leslie G. "The complexity of computing the permanent."
  Theoretical computer science 8.2 (1979): 189-201.</p>
</blockquote>

CC BY-SA 3.0
2017-04-09T04:10:49.387Z
For #P I'm pretty sure the answer is yes. For "counting complexity" more generally I don't know...
Joshua Grochow
<cc.complexity-theory><reference-request><counting-complexity><ho.history-overview>
Was counting complexity first introduced by Valiant in 1979?
Ralff
# Was counting complexity first introduced by Valiant in 1979?

(Asked by: username_0 on 2017-04-09)

Was #P first introduced in [[1]](https://sites.math.washington.edu/~billey/colombia/references/valiant.permanent.1979pdf.pdf)?

> [1] Valiant, Leslie G. "The complexity of computing the permanent."
> Theoretical computer science 8.2 (1979): 189-201.

**Tags:** cc.complexity-theory, reference-request, counting-complexity, ho.history-overview

> **Comments:**
> **username_1**: For #P I'm pretty sure the answer is yes. For "counting complexity" more generally I don't know...  

---

## 1 answers

### Answer by username_2 on 2017-04-14. Score: 9 | Accepted answer

Yes, the complexity class $\mathsf{\#P}$ is first introduced in Valiant's seminal paper "The complexity of computing the permanent." TCS, (1979). This is very clear. As for the terminology, strictly speaking, Valiant does not use the term "counting complexity" in this paper. Instead, he speaks of "counting problems" in several places. In any case, it is probably hard to tell who coined these terms first, but this is probably also not very important.

What remains important is the fact that the complexity class $\mathsf{PP}$ (which, intuitively, is the decision-theoretic variant of $\mathsf{\#P}$) had already been introduced in 1974, by Gill's seminal paper "Computational complexity of probabilistic Turing machines". In this sense, Valiant was very much influenced by Gill's work. In fact, Valiant cites Gill's paper and loosely tells that #P is essentially equivalent to $\mathsf{PP}$ (which is not meant in the strict, formal sense).


---

