I'd like to know about the complexity of the problem below. I believe it might not be possible to solve this with a polynomial time algorithm, but I'd be very happy to be proved wrong.
Problem: Given a sequence of real numbers $a_{1},\dots,a_{n}$ and a collection of subsets $S_{1},\dots,S_{d}\subset\{1,\dots,n\}$, find a subset of the subsets $I\subset\{1,\dots,d\}$, such that their union $S=\cup_{i\in I}S_{i}$, satisfies
$$ \sum_{j\in S}a_{j}>0 $$
or prove that no such subset exists.
I'm interested in the worst-case complexity, in particular dealing with cases where the 'no such such subset exists' result is the answer. Thanks for reading!
Even finding out whether such an $I$ exists is NP-complete.
Assuming a computationally reasonable representation of the "real" numbers $a_i$, it is easy to see that the problem is in NP: If the answer is "yes", that answer can be certified by writing down explicitly an $I$ that works, and this certificate can clearly be checked in polynomial time
For NP-hardness, we can reduce from the Set Cover problem:
Given a family of $k$ subsets $A_i\subseteq \{1,2,\ldots,m\}$ we want to find out whether there are $p$ of the subsets whose union is all of $\{1,2,\ldots,m\}$.
Define $$ a_j = \begin{cases} 1 & 1 \le j \le m \\ -\frac1{p+1} & m+1 \le j \le m+k \\ -m+1 & j = m+k+1 \end{cases} $$ and $$ S_i = A_i \cup\{m+i\}\cup\{m+k+1\} $$ This is an instance of your problem with $n=m+k+1$ and $d=k$, where an $I\subseteq\{1,\ldots,k\}$ has $\sum a_j>0$ exactly it it consists of at most $p$ of the $A_i$s that together cover $\{1,2,\ldots,m\}$.