Given multiset of integers $a_1,\dots,a_{m}$ where $|a_i|\leq\log^cm$  for some $c\in\Bbb R^+$. Is it $\mathsf{NP}$-complete to decide if there is a cardinality $\lceil m^\alpha\rceil$ submultiset for some $\alpha\in(0,1)$ whose sum is $0$?How many submultisets of such cardinality can we expect to have vanishing sum?
On submultisets of given cardinality and bound that sum to $0$
complexity theory;np complete;decision problem
Assuming that $c$ is fixed, this can be solved using dynamic programming in quasipolynomial time. We compute inductively all possible sums of all submultisets of size $k$ for all $k \leq \lceil m^\alpha \rceil$. Since each such sum is at most $2^{\log^c m} \lceil m^\alpha \rceil$, this algorithm runs in $O(2^{O(\log^c m)} m^{O(1)})$, which is quasipolynomial. This suggests that the problem is not NP-hard.