June 2014
Intermediate to advanced
512 pages
17h 55m
English
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.