3
$\begingroup$

I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$, $D_1$ and $D_2$, find all sequences $a_1\lt a_2 \lt \dots \lt a_n$ are there such that:

  1. each $a_i\in\{1, \dots, m\}$
  2. $\sum_{i=1}^n a_i = D_1$
  3. $\sum_{i=1}^n a_i^2 = D_2$.

I want to know the complexity with respect to $m$, $n$, $D_1$ and $D_2$.

For example, when $m=12$, $n=4$, $D_1=26$ and $D_2=214$ the solutions are

$$ 3,5, 6, 12\qquad 2, 5, 8, 11\qquad 1, 7, 8, 10$$

$\endgroup$
  • $\begingroup$ This seems as modification of subset sum for 1..m range. $\endgroup$ – rus9384 Aug 30 '17 at 11:15
  • $\begingroup$ @rus9384 The simultaneous restriction on the sum of squares makes this look like a completely different problem, to me. $\endgroup$ – David Richerby Aug 30 '17 at 12:25
  • $\begingroup$ @DavidRicherby, yet it does not mean that subset sum is not reducible to this. $\endgroup$ – rus9384 Aug 30 '17 at 12:43
  • $\begingroup$ @rus9384 Sure. Any problem might reduce to it. Saying that alone doesn't help at all: the nonlinear nature of the constraints here make the reduction look really difficult. $\endgroup$ – David Richerby Aug 30 '17 at 12:54
1
$\begingroup$

Here is a simple recursive solution that runs in exponential time.

Geometrically you want to enumerate the lattice points which lies inside the first quadrant of the $n$-hypercube of height $m$ and on the intersection of the $D_1$-radius $L_1$ sphere and the $D_2$-radius $L_2$ sphere (let call them respectively $S_1$ and $S_2$), up to reordering of the coefficients.

Denoting by $V_n$ the volume of the $n$ unit dimensional ball, we have :

  • $m^n/n!$ points in the intersection of the hypercube and the quadrant (let's call it $D$) with the ordering ,
  • $\alpha = O\left(m^n e^{\frac{-(D_1-nm/6)^2}{3nm}}\right)$ in $S_1\cap D$ (see theorem 1.3 of http://www.doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf), considering the ordering condition.
  • $\beta = \frac{1}{n!2^{n}}V_n D_2^{n/2} + O\left(D_2^{n/2-1+\epsilon}\right)$ in $S_2$ (Generalized Gauss circle problem+quadrant condition+order condition). I'm not considering intersection with the hypercube here, so the global complexity will be an overestimation.

Depending on your parameters choose the minimum of $\alpha$ or $\beta$. If its $\alpha$ perform a recursive enumeration of the integers partitions of length $n$ with the restriction on $m$ and use early abort to discard solutions which are getting out $S_2$. In the other case, enumerate the lattice point on $S_2$ ( with recursive orthogonal projections for instance) and check for the appartenance in $S_1$ for each returned vector.

Hence the global complexity will be dominated by $min(\alpha, \beta)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think $D_1$-radius $L_1$ should be a hyperplane instead of a sphere. Though I've no idea whether it is computable when $m$ & $n$ are large (~hundreds). Thanks $\endgroup$ – Steve Yau Sep 1 '17 at 1:44
  • $\begingroup$ The intersection of the hyperplane with the hypercube is the same as the intersection of the $L_1$ sphere and the hypercube. I've doubts on the tractability in high dimension indeed... Enumeration of the ball up to dimension lower than a hundred is feasible nonetheless. $\endgroup$ – Sn0w Sep 1 '17 at 15:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.