I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a slight change to it:

Suppose, you have a box $B$ with $n$ items and you pull $k<n$ items out of it. Items have different (positive integer) sizes $s_i$, with larger items being more probable to get pulled out: $$p(i) = \frac{s_i}{\sum_{\forall j\in B}{s_j}}$$ Is the expected probability that an item $i$ will be among the $k$ items you will have pulled out of the box greater than (a finite decimal number) $x$?

I could not find a straightforward way to even show that it's in $\mathsf{MA}$. On the other hand, I also could not find a way to show $\mathsf{NP}$-hardness.

  • $\begingroup$ I assume the probability adjusts every time an item is pulled? So it gets bigger if a very large item gets removed? I'd first try to figure out how to calculate the probability at all. $\endgroup$
    – gnasher729
    Nov 24, 2023 at 15:55
  • $\begingroup$ Yes, the probability is just the weight of the item divided by the weight of all items remaining in the box at the moment you pull it out. That way removing an item from a box creates a problem instance of a smaller size, like as if you assigned one variable in SAT. $\endgroup$
    – rus9384
    Nov 24, 2023 at 16:31
  • $\begingroup$ @D.W. Clarified it, though whether it's a decimal or a binary fraction should not affect the complexity. Basically, it's just a decision variant (so you could use the binary search) of computing $O(n)$ first digits of the probability that $i$ will be among the $k$ items. $\endgroup$
    – rus9384
    Nov 25, 2023 at 0:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.