Corollary 9.16
For any function f in #P, we may define a set 
. Then, 
. By Theorem 9.6, we know that for all functions f, f is #P-complete if and only if Af is complete for PP under the 
-reducibility. Therefore, the class PP has many 
-complete sets. In the following, we show that some of these sets are actually complete for PP under the stronger 
-reducibility.
Theorem 9.17
Proof
Get Theory of Computational Complexity, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
