If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear inequalities then is there a procedure when the conditions of exponentiation are base is constant and all involved variables (including the exponent) are always rational? If so what is the complexity?


In essence we have $n$ formulas of type
$$x\_i R\_1 a$$
$$x\_i R\_1 x\_j$$
$$x\_i R\_2 2^{x\_j}$$
where $q$ is rational and $R\_1,R\_2\in\{<,>,=,\leq,\geq\}$ and we want to find if $\exists x\_1,\dots,x\_m\in\mathbb Q$ and $n=O(m)$ holds.


What if $R\_2\in\{=\}$?



Linear programming with exponential inequalities and rational variables
Consider questions like whether $${\large{2^{2^{\sqrt{2^\phantom{o\!}}}}}}>\frac{19}{3}.$$
That inequality is true, but I think we don't know whether expressions like the left-hand side can be rational. So we don't know how accurately we need to compute towers of exponentials to see if inequalities hold.


In terms of your phrasing, I don't think we have any algorithm to settle if there are rational solutions for systems of inequalities like
$$2^{1/2}>q,\ \ 2^q>r,\ \ 2^r>\frac{19}{3}.$$


Update: If exponentiation occurs only in the form $x\_i = 2^{x\_j}$, then rational solutions must have integral $x\_j$, and there is an algorithm.


