# Assignment of values for a set

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?

• They are a part of input. The variables x_i's must respect this bound. – Star Aug 12 '15 at 15:19

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.
• This is not a correct answer. As the feasible x values do not necessarily respect the bound. – Star Aug 13 '15 at 5:17
• 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. – Klaus Draeger Aug 13 '15 at 8:39
• $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. – Star Aug 13 '15 at 9:08
• 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? – Klaus Draeger Aug 13 '15 at 10:59
• 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$ – Klaus Draeger Aug 13 '15 at 12:53