Corollary 9.16

For any function f in #P, we may define a set c09-math-0687. Then, c09-math-0688. 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 c09-math-0693-reducibility. Therefore, the class PP has many c09-math-0694-complete sets. In the following, we show that some of these sets are actually complete for PP under the stronger c09-math-0695-reducibility.

Theorem 9.17

Proof

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.