Was #P first introduced in [1]?
[1] Valiant, Leslie G. "The complexity of computing the permanent." Theoretical computer science 8.2 (1979): 189-201.
$\begingroup$
$\endgroup$
1
-
9$\begingroup$ For #P I'm pretty sure the answer is yes. For "counting complexity" more generally I don't know... $\endgroup$– Joshua GrochowCommented Apr 9, 2017 at 4:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
