0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What did you try and where are you stuck? $\endgroup$ – Pål GD Jan 28 at 21:42
  • $\begingroup$ 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%. $\endgroup$ – user109711 Jan 29 at 5:00
  • $\begingroup$ 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. $\endgroup$ – user109711 Jan 29 at 5:00
  • $\begingroup$ 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|$. $\endgroup$ – user109711 Jan 29 at 5:00
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 30 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.