Relating to a question I posted here, I have formulated the following question:
Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$.
How to check the following system of equations is feasible? Assumption: $x_i, b_k$ are all in $[0,1]$
$\max\{x_i\mid i\in J_k\}=b_k$ where $1\leq k\leq m$ and $J_k\subseteq \{1, \cdots, n\}$
for example:
$\max\{x_1, x_4\}=0.7$ and $\max\{x_1, x_2, x_3\}=0.5$
What's the complexity of this problem? Obviously it is in NP, but is it NP-hard? It would be a surprise if such an easy problem does not have a polynomial algorithm. Does linear programming help here?
Many thanks.