Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that

(i) $0 \le p_1, \ldots, p_n \le 1$

(ii) For $1\le j \le k$, $|(\sum_{i=1}^n p_i^j) - \alpha_j|\le \epsilon$.

Here $k \ll n$. I am interested in the time complexity of this problem: In particular, based on some symmetry considerations, one can show that it suffices to restrict one's search to the case where $p_1, \ldots, p_n$ all come from a set of size at most k. Based on this observation, one can consider all possible ways of partitioning $p_1, \ldots, p_n$ into k sets (which takes time $n^k$) and subsequently solve a problem which requires one to solve polynomial equations over the reals (in k variables and of degree bounded by k). This takes time $k^k$. The dependence of n^k is prohibitive for me and I was wondering if there is a way to solve this in time $O(n^{O(1)} \cdot k^{k})$ or at least better than $n^k$.

  • 3
    $\begingroup$ cross-posted: cstheory.stackexchange.com/questions/30678/… $\endgroup$
    – usul
    Mar 4 '15 at 3:47
  • $\begingroup$ @Anindya De Can you give some context to this question? Like any paper that motivated you to ask this? $\endgroup$
    – user6818
    Mar 4 '15 at 20:32
  • $\begingroup$ So you are looking for numbers whose norms are bound? Did you try simplest case $\alpha_j=\alpha$? $\endgroup$
    – Mr.
    Mar 5 '15 at 4:20
  • $\begingroup$ In a sense you are looking at intersection of $k$ varieties of polynomials $f_j(x_1,\dots,x_n)-\alpha_j-\eta=0$ where $\eta\in(-\epsilon,\epsilon)$ with cube $[0,1]^n$? $\endgroup$
    – Mr.
    Mar 5 '15 at 4:27
  • $\begingroup$ Obviously intersection of $f_j(x_1,…,x_n)−α_j−η=0$ will have a solution in $(x_1,\dots,x_k,0,\dots,0)$. However this may lie elsewhere outside $[0,1]^n$. $\endgroup$
    – Mr.
    Mar 5 '15 at 5:54

The system has a very special structure, that prompts a different approach (classically known as Prony method): one can parametrise the $p_i$ as the roots of a polynomial $f(t)=\sum_{\ell=0}^n f_\ell t^\ell.$ Then for the case $\epsilon=0$ and $k\gg n$ one has that $(f_0,\dots,f_n)$ is in the kernel of the Hankel matrix $$ \begin{pmatrix}a_1&a_2&\dots &a_n\\ a_2& a_3&\dots &a_{n+1}\\ \dots\\ a_n& a_{n+1}&\dots & a_{2n-1} \end{pmatrix} $$ as you can multiply the (truncated) Vandermonde matrix depending on $p_i$ by $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) on the left, obtaining zeros, which should equal to the scalar product of $(f_0,\dots,f_n)^\top$ (and by the corresponding vectors of coefficients of $tf(t)$, $t^2 f(t)$, etc.) and $(a_1,a_2,\dots)$.

Perhaps this kind of parametrisation will give a much for efficient procedure.

  • $\begingroup$ I forgot to add: In our case, $k \ll n$. $\endgroup$
    – Anindya De
    Mar 4 '15 at 3:33
  • 1
    $\begingroup$ well, my answer was to highlight the fact that in a similar setting complexity of solving is much better than exponential. $\endgroup$ Mar 4 '15 at 9:44

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.