Let $G = \mathbb{Z}/n\mathbb{Z}$ be the cyclic group of order $n$. Suppose we are given a vector $g = (g_1, \ldots, g_m) \in G^m$ as input along with the sets $S_1, \ldots, S_k \subseteq [m]$. Define the operators $T_i \colon G^m \to G^m$ as follows. If $j \in S_i$ then $(T_i g)_j = g_j + 1$ and if $j \notin S_i$ then $(T_i g)_j = g_j$. To be clear, addition is done modulo $n$. Also, note that the operators commute (i.e. $T_i T_j = T_j T_i$ for all $i,j$).
Define the score function $s \colon G^m \to \mathbb{N}$ as $s(g) = g_1 + \ldots + g_m$ where addition is done over $\mathbb{N}$ (not over $G$). The problem is to find a sequence of operations on $g$ to maximize its score. Since each $T_i$ commute, the problem is to determine a vector $(N_1, \ldots, N_k)$ such that the score of $(\prod_i T_i^{N_i}) g$ is maximized.
Here is an example. Suppose $n = 3$, $m = 4$, and $k = 2$. The input vector is $g = (0,0,0,0)$ and $S_1 = \{1,2,3\}$, $S_2 = \{2,3,4\}$. Thus $T_1 g = (1,1,1,0)$ and $T_2 g = (0,1,1,1)$. Also $s(g) = 0, s(T_1g) = s(T_2g) = 3$. Also, $T_1^2 T_2 g = (2,0,0,1)$ because we incremented the first coordinate twice, the second and third coordinate 3 times and the last coordinate only once.
In the above example, the maximum score is $6$ and we can see this by enumerating all the possible $(N_1, N_2)$ values and computing the score of $T_1^{N_1} T_2^{N_2}g$. Indeed, $(2,0), (0,2), (2,2)$ gives a score of 6.
My questions are as follows. I could not find this puzzle anywhere. Does this puzzle or a simpler variant of it appear anywhere in the literature?
The only algorithm I could come up with is exhaustive search. Can we do better? Another way to state this question is to consider the decision problem where one is asked to determine if the maximum score is at least some value. This is clearly in NP. Is it also in P?
Sorry, I have to make a correction. The problem to find the maximum value is in theta_2. However, the real problem is to find N_1, ... , N_k which maximize the value. This problem is in the class delta_2, that is the class of problems which can be solved in polynomial time by an algorithm which can ask an arbitrary number of questions to an oracle from NP. It is possible that the first problem is complete in theta_2, and the second problem is complete in delta_2.