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 *A*_{f} 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.

Start Free Trial

No credit card required