<p>Valiant's defines <span class="math-container">$\#\mathsf P$</span> to be the set of functions computable by counting (N)TM which are basically normal polynomial-time NTMs but <em>magically</em> (sic!) output the number of accepting computation paths given some input.</p>
<p>Given this, we can now tackle your questions.</p>
<ol>
<li>If you meant to say that all such witnesses/certificates are verifiable in polynomial time (i.e. <span class="math-container">$X \in \mathsf{NP}$</span>) then your answer is yes; this is basically what all NTMs for <span class="math-container">$\mathsf{NP}$</span> problems do (if you do not arbitrarily design them to have multiple accepting paths per valid certificate or other such things).
However, if some certificates take superpolynomial time to validate, then the answer would be no.</li>
<li>I am not sure what you mean by <em>output complexity</em> here.
If you mean that the time needed for <span class="math-container">$E$</span> to produce all certificates (or solutions) is polynomial in the input/output size then we face the problem that <span class="math-container">$E$</span> can give very long outputs.
I am pretty positive that one can construct problems where an output efficient enumerator exists while counting the number of such solutions is too hard for <span class="math-container">$\#\mathsf P$</span>. In this case, the answer would be no, but I am not quite sure.</li>
</ol>

CC BY-SA 4.0
2020-07-10T07:20:08.247Z
Ah ok, thanks for the explanation! Sorry, I should have been more output complexity, i.e., $X\in \textbf{DelayP}$ [1]. $\textbf{DelayP}$ (Polynomial Time Delay) if the time delay until the output of the first and
between the output of any two consecutive solutions is bounded by a polynomial in
the input size. [1] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123,
1988.
BotNzd
CC BY-SA 4.0
2020-07-09T03:12:04.490Z
2020-07-09T03:12:04.490Z
Watercrystal
<p>The answer is yes. But I'd like to correct one small mistake in your question: Valiant defined #P in terms of a counting TM, which is a <strong>polynomial-time</strong> NTM that has the additional capability of outputting the number of solutions. Here &quot;polynomial-time&quot; means that the longest length of solution (more technically, the longest length of accepting path / witness) for <span class="math-container">$n$</span>-bit input string is at most polynomial in <span class="math-container">$n$</span>.</p>
<p>From the definition, it is straightforward to conclude that if a decision problem <span class="math-container">$X$</span> is in NP, then the corresponding counting problem #<span class="math-container">$X$</span> is in #P. This should answer your first question.</p>
<p>As to the second question, an efficient enumeration algorithm implies that not only the decision problem is in P, but also counting the number of solutions is also efficient, therefore belongs to the complexity class #P (in fact, belongs to a much more tractable complexity class called FP).</p>
<p>By the way, I feel like Valiant's definition is a little bit misleading, I prefer another definition from the book <em>Computational Complexity: A Mordern Approach</em>: A function <span class="math-container">$f:\{0,1\}^*\rightarrow \mathbb{N}$</span> is in #P if there exists a polynomial <span class="math-container">$p$</span> and a polynomial-time TM <span class="math-container">$M$</span> such that for every <span class="math-container">$x\in \{0,1\}^*$</span>, <span class="math-container">$f(x) = \left| \left\{ y \in \{0,1\}^{p(|x|)}: M(x,y)=1 \right\} \right|$</span>.</p>

CC BY-SA 4.0
2020-07-10T07:33:34.127Z
Thanks for the clarification. Good points about polynomial-time and the enumeration. Unfortunately, I was also for the second part unprecise. For the second question, let ∈  [1]. $X$ is in  (Polynomial Time Delay) if the time delay until the output of the first and between the output of any two consecutive solutions is bounded by a polynomial in the input size. [1] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988.
BotNzd
CC BY-SA 4.0
2020-07-09T02:38:47.107Z
2020-07-09T02:38:47.107Z
Conn-CaoYK
<p>Valiant defined <span class="math-container">$\#P$</span> in terms of a <em>counting TM</em>, which is a NTM that outputs the number of solutions [1].</p>
<p>I am a bit stuck with the following two questions:
Let's say I have a decision problem <span class="math-container">$X$</span>, the corresponding counting problem <span class="math-container">$\#X$</span>, and an enumeration algorithm <span class="math-container">$E$</span> that enumerates the solutions of <span class="math-container">$X$</span> in polynomial output complexity.</p>
<ol>
<li>If <span class="math-container">$w$</span> is a witness for <span class="math-container">$X$</span> that I can verify in polynomial time, does this imply that <span class="math-container">$\#X$</span> is in <span class="math-container">$\#P$</span>?</li>
<li>Does the existence of <span class="math-container">$E$</span> imply that <span class="math-container">$\#X$</span> is in <span class="math-container">$\#P$</span>?</li>
</ol>
<p>For both questions, I think the answer is yes because they imply that there is a NTM which could be modified to count the number of witnesses. However, I feel like I cannot argue this properly and that I might miss something.</p>
<p>[1] Leslie G. Valiant: The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189-201 (1979)</p>

<complexity-theory>
Understanding definition of #P
BotNzd
# Understanding definition of #P

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

Valiant defined $\#P$ in terms of a *counting TM*, which is a NTM that outputs the number of solutions [1].

I am a bit stuck with the following two questions:
Let's say I have a decision problem $X$, the corresponding counting problem $\#X$, and an enumeration algorithm $E$ that enumerates the solutions of $X$ in polynomial output complexity.

1. If $w$ is a witness for $X$ that I can verify in polynomial time, does this imply that $\#X$ is in $\#P$?
2. Does the existence of $E$ imply that $\#X$ is in $\#P$?

For both questions, I think the answer is yes because they imply that there is a NTM which could be modified to count the number of witnesses. However, I feel like I cannot argue this properly and that I might miss something.

[1] Leslie G. Valiant: The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189-201 (1979)

**Tags:** complexity-theory


---

## 2 answers

### Answer by username_1 on 2020-07-09. Score: 0 | Accepted answer

Valiant's defines $\#\mathsf P$ to be the set of functions computable by counting (N)TM which are basically normal polynomial-time NTMs but *magically* (sic!) output the number of accepting computation paths given some input.

Given this, we can now tackle your questions.

1. If you meant to say that all such witnesses/certificates are verifiable in polynomial time (i.e. $X \in \mathsf{NP}$) then your answer is yes; this is basically what all NTMs for $\mathsf{NP}$ problems do (if you do not arbitrarily design them to have multiple accepting paths per valid certificate or other such things).
   However, if some certificates take superpolynomial time to validate, then the answer would be no.
2. I am not sure what you mean by *output complexity* here.
   If you mean that the time needed for $E$ to produce all certificates (or solutions) is polynomial in the input/output size then we face the problem that $E$ can give very long outputs.
   I am pretty positive that one can construct problems where an output efficient enumerator exists while counting the number of such solutions is too hard for $\#\mathsf P$. In this case, the answer would be no, but I am not quite sure.

> **Comments:**
> **username_0**: Ah ok, thanks for the explanation! Sorry, I should have been more output complexity, i.e., $X\in \textbf{DelayP}$ [1]. $\textbf{DelayP}$ (Polynomial Time Delay) if the time delay until the output of the first and between the output of any two consecutive solutions is bounded by a polynomial in the input size. [1] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988.  

---

### Answer by username_2 on 2020-07-09. Score: 0

The answer is yes. But I'd like to correct one small mistake in your question: Valiant defined #P in terms of a counting TM, which is a **polynomial-time** NTM that has the additional capability of outputting the number of solutions. Here "polynomial-time" means that the longest length of solution (more technically, the longest length of accepting path / witness) for $n$-bit input string is at most polynomial in $n$.

From the definition, it is straightforward to conclude that if a decision problem $X$ is in NP, then the corresponding counting problem #$X$ is in #P. This should answer your first question.

As to the second question, an efficient enumeration algorithm implies that not only the decision problem is in P, but also counting the number of solutions is also efficient, therefore belongs to the complexity class #P (in fact, belongs to a much more tractable complexity class called FP).

By the way, I feel like Valiant's definition is a little bit misleading, I prefer another definition from the book *Computational Complexity: A Mordern Approach*: A function $f:\{0,1\}^\*\rightarrow \mathbb{N}$ is in #P if there exists a polynomial $p$ and a polynomial-time TM $M$ such that for every $x\in \{0,1\}^\*$, $f(x) = \left| \left\{ y \in \{0,1\}^{p(|x|)}: M(x,y)=1 \right\} \right|$.

> **Comments:**
> **username_0**: Thanks for the clarification. Good points about polynomial-time and the enumeration. Unfortunately, I was also for the second part unprecise. For the second question, let ∈  [1]. $X$ is in  (Polynomial Time Delay) if the time delay until the output of the first and between the output of any two consecutive solutions is bounded by a polynomial in the input size. [1] David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988.  

---

