Solving a Min/Max equation set
To follow up on Snowie's post:

For each term max(v1, v2) introduce a new variable $x_i$, subject to the constraints $x_i \geq v_1, x \geq v_2$

For each term min(v1,v2) introduce a variable $y_i$ subject to $y_i \leq v_1, y_i \leq v_2$.

Next, minimize the linear constraint $l = \sum x_i - \sum y_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.

This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.