# Is summing a function over all subsets in PP?

Consider the following decision problem:

Input: a set $$X = \{x_1, \ldots, x_n\}$$, a mapping $$f \colon 2^X \mapsto \mathbb{N}$$ such that for $$f(Y)$$ is computed in polynomial time for any $$Y \subseteq X$$, and an integer $$k \in \mathbb{N}$$.

Question: does $$\sum_{Y \subseteq X}{f(Y)} \geq k$$ hold?

1. Is this problem in the complexity class $$\mathsf{PP}$$? If yes, which NP Turing machine decides it?

Additionally, for proving such a membership result:

1. Should we specify how $$f$$ is represented?

2. Should we assume that $$f$$ is polynomially bounded?

• What did you try and where are you stuck? – Pål GD Jan 28 at 21:42
• 1) What I had in mind is to solve the problem through a NP Turing machine where the acceptance condition is that a majority (more than half) of computation paths accept. My intuition is that the problem is in PP as an NP machine induces a tree of depth n that allows to capture all subsets Y of X. At each leaf, it could compute f(Y) and somehow create f(X) accepting branches. Then additional accepting / rejecting branches would be created somewhere to make the rate of accepting states to 50%. – user109711 Jan 29 at 5:00
• The problem is I lack experience with this class. I am more familiar with non-deterministic algorithms such as "1. guess a succinct candidate w; 2. check in polytime that w is a proof that the instance is a yes one" to prove membership in NP, than with Turing machines. – user109711 Jan 29 at 5:00
• 2) I believe the representation of f needs not to be specified, if one wants to show membership for any f satisfying that definition. 3) I believe f needs not to be polynomially bounded, as the depth of the accepting / rejecting branches from the NP machine in point 1) would still be a polynomial in $|X|$. – user109711 Jan 29 at 5:00
• The answer really depends on how $f$ is specified. If it is specified as a table of values, then you can compute the sum in linear time. – Yuval Filmus Jan 30 at 5:24