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.
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)
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.
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP