<p>The problem as stated now is solvable in linear time.</p>

<p>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).</p>

<p>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$.</p>

<p>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$.</p>

<p>EDIT: What we have are the following results:</p>

<ul>
<li>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$.</li>
<li>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$.</li>
<li>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. </li>
</ul>

CC BY-SA 3.0
2015-08-13T05:17:12.867Z
This is not a correct answer. As the feasible x values do not necessarily respect the bound.
Star
CC BY-SA 3.0
2015-08-13T08:39:23.447Z
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
CC BY-SA 3.0
2015-08-13T09:08:20.683Z
$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
CC BY-SA 3.0
2015-08-13T10:59:15.450Z
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
CC BY-SA 3.0
2015-08-13T12:34:48.240Z
Sorry but consider $p=(0.5,0.5)$. Then this contradicts with your statement in part (a) of your EDIT version. You cannot claim that $p=x=w=e_k$ even if you get rid of the bounds for $x,w$ variables.
Star
CC BY-SA 3.0
2015-08-13T12:53:15.017Z
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
CC BY-SA 3.0
2015-08-13T12:57:19.390Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/26927/discussion-between-star-and-klaus-draeger).
Star
CC BY-SA 3.0
2015-08-12T23:55:38.973Z
2015-08-13T10:55:51.810Z
2015-08-13T10:55:51.810Z
Klaus Draeger
<p>Consider the following problem:</p>

<p><strong>Input</strong>: 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$.</p>

<p>Let </p>

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

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

<p><strong>Query</strong>: 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$?</p>

<p>What is the complexity of this problem?</p>

CC BY-SA 3.0
2015-08-12T15:19:59.490Z
They are a part of input. The variables x_i's must respect this bound.
Star
<cc.complexity-theory><ds.algorithms><time-complexity><convex-optimization><convex-geometry>
Assignment of values for a set
Star
# Assignment of values for a set

(Asked by: username_0 on 2015-08-12)

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?

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity, convex-optimization, convex-geometry

> **Comments:**
> **username_0**: They are a part of input. The variables x_i's must respect this bound.  

---

## 1 answers

### Answer by username_1 on 2015-08-12. Score: 3

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.

> **Comments:**
> **username_0**: This is not a correct answer. As the feasible x values do not necessarily respect the bound.  
> **username_1**: 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.  
> **username_0**: $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.  
> **username_1**: 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?  
> **username_0**: Sorry but consider $p=(0.5,0.5)$. Then this contradicts with your statement in part (a) of your EDIT version. You cannot claim that $p=x=w=e_k$ even if you get rid of the bounds for $x,w$ variables.  
> **username_1**: 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$  
> **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/26927/discussion-between-star-and-klaus-draeger).  

---

