TransWikia.com

Understanding definition of #P

Theoretical Computer Science Asked on October 30, 2021

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)

2 Answers

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.

Answered by Watercrystal on October 30, 2021

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 $xin {0,1}^*$, $f(x) = left| left{ y in {0,1}^{p(|x|)}: M(x,y)=1 right} right|$.

Answered by Conn-CaoYK on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP