0
$\begingroup$

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\{=\}$?

Improve this question
$\endgroup$
1
  • $\begingroup$ You might want to look at the paper "Deciding polynomial transcendental problems" by McCallum and Weispfenning. $\endgroup$
    – Erik Walsberg
    Commented Oct 3, 2020 at 2:13

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .