Let f(x,y) be a #P function and r(x) a polynomial-time computable function bounded by a polynomial in |x|.
- The sum of f(x,y) for all y with |y| = r(x) is in #P.
- The product of f(x,y) for all y with 1 ≤ y ≤ r(x) is in #P.
- (f(x,0) choose r(x)) is in #P.
L is in PP if there is a #P function f and a polynomial-time computable r such that
- x in L implies f(x) ≥ r(x)
- x not in L implies f(x) < r(x).
L is in ⊕P if there is a #P function f such that
- x in L implies f(x) is odd
- x not in L implies f(x) is even
L is in UP if there is a #P function f such that
- x in L implies f(x) = 1
- x not in L implies f(x) = 0
We also proved the Valiant-Vazirani theorem: There is a polynomial q and a probabilistic polynomial-time function f mapping CNF formulas to CNF formulas such that
- If φ is not satisfiable then f(φ) is never satisfiable.
- If φ is satisfiable then with probability at least 1/q(n), f(φ) has a unique satisfying assignment.
Link:
- NP is as easy as detecting unique solutions by Les Valiant and Vijay Vazirani. We gave Noam Ta-Shma's proof of Mulmuley-Vazirani-Vazirani isolation lemma. See also my blog post.
