-1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – BotNzd Jul 10 '20 at 7:20
0
$\begingroup$

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|$.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – BotNzd Jul 10 '20 at 7:33

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.