1
$\begingroup$

Consider the following problem:

Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$.

Let

  • $P = \{ \vec{p} \in \times_{i=1}^{n} [a_i,b_i] : ||\vec{p}||_1 = 1\}$,
  • $X = \{ \vec{x} \in \times_{i=1}^{n} [l_i,u_i] : ||\vec{x}||_1 = 1\}$,
  • $W = \{ \vec{w} \in [0,1]^n : ||\vec{w}||_1 = 1\}$,

where $||\vec{v}||_1 = \sum_{i=1}^n v_i$.

Query: for all $\vec{p} \in P$ there are $\vec{x} \in X$ and $\vec{w} \in W$ such that $x_iw_i=p_i$ for all $i = 1, \ldots, n$?

What is the complexity of this problem?

$\endgroup$
1
  • $\begingroup$ They are a part of input. The variables x_i's must respect this bound. $\endgroup$
    – Star
    Aug 12, 2015 at 15:19

1 Answer 1

3
$\begingroup$

The problem as stated now is solvable in linear time.

To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\sum_{i=1}^np_i=\sum_{i=1}^nx_iw_i$, but on the other hand because of $1 = \sum_{i=1}^nx_i$ and $1 = \sum_{i=1}^nw_i$ we have $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$, so that $x_iw_j$ must be $0$ for all $i\neq j$ (using also that all the $x_i,w_i$ are nonnegative).

This implies that there is some index $k$ with $x_k=w_k=1$ and $x_j=w_j=0$ for all other $j$: indeed, since $1 = \sum_{i=1}^nx_i$, some $x_k$ must be nonzero. Then $x_kw_j=0$ means $w_j=0$ for all $j\neq k$, and because $1 = \sum_{i=1}^nw_i$, we have $w_k=1$. Analogously we get $x_j=0$ for $j\neq k$ and $x_k=1$. As a consequence, $p_k=1$ and $p_j=0$ for $j\neq k$.

The decision problem is whether this is true for all $p\in P$. Since $P$ is convex, this is only possible if $P$ only consists of one of these unit vectors, i.e. for some $k$ we have $a_k=b_k=1$ and $a_j=b_j=0$ for all other $j$; additionally, $X$ must also contain this vector, i.e. we need to have $u_k=1$ and $l_j=0$ for $j\neq k$.

EDIT: What we have are the following results:

  • If $p,x,w\in[0,1]^n$ with $\sum_ip_i=\sum_ix_i=\sum_iw_i=1$ and $p_i=x_iw_i$ for all $i$, then $p=x=w=e_k$ for some $k$, where $e_k$ is the unit vector given by $(e_k)_k=1$ and $(e_k)_j=0$ for all $j\neq k$.
  • Adding the constraints $a_i\le p_i\le b_i$ and $l_i\le x_i\le u_i$ further restricts the set of solutions to those $e_k$ which are both in $P$ and in $X$, i.e. such that $b_k=u_k=1$ and $a_j=l_j=0$ for $j\neq k$.
  • The decision problem given in the question is whether such $x,w$ exist for all $p\in P$; the answer to this is "yes" if and only if $P$ is a singleton set $\{e_k\}$ for some $k$, i.e. $a_k=b_k=1$ and $a_j=b_j=0$ for $j\neq k$, and additionally this $e_k$ is in $X$, i.e. $u_k=1$ and $l_j=0$ for $j\neq k$. This can be checked in linear time.
$\endgroup$
7
  • $\begingroup$ This is not a correct answer. As the feasible x values do not necessarily respect the bound. $\endgroup$
    – Star
    Aug 13, 2015 at 5:17
  • 1
    $\begingroup$ The only bounds on the $x$ values I see in the question are $l_i\le x_i\le u_i$ and $x_1+\dots+x_n=1$; these are ensured by the requirement that $X$ contain the unit vector in question. $\endgroup$ Aug 13, 2015 at 8:39
  • $\begingroup$ $X$ contains unit vectors but those whose elements respect the given interval bounds. In your argument, $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$ you conclude that there is some index $k$ such that $x_k=w_k=1$. That might not be really the case. As for some realization of the $p$ vector, you may not be able to find values for $w$ and $x$ such that the $p=w.x$ constraint is satisfied. $\endgroup$
    – Star
    Aug 13, 2015 at 9:08
  • 2
    $\begingroup$ Yes, but that part of the argument only shows the consequences of the norm and product constraints. That the vectors need to also satisfy the bounds then further restricts the possibilities. I have added a summary of the results - does this help? $\endgroup$ Aug 13, 2015 at 10:59
  • 2
    $\begingroup$ Yes, but the point is that then there are no $(x_1,x_2)$ and $(w_1,w_2)$ in $[0,1]^2$ with $x_1+x_2=w_1+w_2=1$ and $x_1w_1=x_2w_2=0.5$ $\endgroup$ Aug 13, 2015 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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