# Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $$\exists x\in\mathbb R^n:Ax\leq b$$ is standard linear program.

I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications and no alternations.

Can we always solve programs of type $$\exists x_1\in\mathbb R^{n_1}\dots\exists x_t\in\mathbb R^{n_t}$$$$A_1[x_1,x_2]^T\leq b_1\wedge\dots\wedge A_{t-1}[x_{t-1},x_t]^T\leq b_{t-1}$$ and $$\exists x_1\in\mathbb R^{n_1}\dots\exists x_t\in\mathbb R^{n_t}$$$$A_1[x_1,x_2]^T\leq b_1\wedge A_2[x_1,x_2,x_3]^T\leq b_2\wedge\dots\wedge A_{t-1}[x_1,\dots,x_{t-1},x_t]^T\leq b_{t-1}$$ in time $$\mathsf{poly}(t,\sum_{i=1}^t(m_i+n_i))$$ where $$A_i$$ are matrices in $$\mathbb R^{m_i\times n_i}$$ and $$b_i$$ are vectors in $$\mathbb R^{m_i}$$ by collapsing the quantifications into one single big $$\exists$$ quantifier and considering as a standard linear program and solving via standard linear programming techniques?

Or is it possible there are scenarios where the program would require time $$\big(\sum_{i=1}^t(m_i+n_i)\big)^{2^{O(t)}}\mathsf{poly}(t,\sum_{i=1}^t(m_i+n_i))$$ (which is the complexity if we use Fourier Motzkin elimination according to https://www3.risc.jku.at/projects/intas/Timisoara/Presentations/German/Grman.pdf if we have alternating quantifiers and perhaps no free variables)?

In this introductory blog post https://cstheory.blogoverflow.com/2011/11/something-you-should-know-about-quantifier-elimination-part-i/ it is mentioned in the very last line that "I do not know if a doubly exponential lower bound is known for the decision problem when there are no free variables".

I want to know if this comment applies to scenarios of no alternations.

• "Can we always solve programs of type $$\exists x_1\in\mathbb R^{n_1}\dots\exists x_t\in\mathbb R^{n_t}$$$$A_1[x_1,x_2]^T\leq b_1\wedge\dots\wedge A_{t-1}[x_{t-1},x_t]^T\leq b_{t-1}$$ I don't understand -- why can't this, as stated, be interpreted as just a single linear program? Isn't it just a system of linear inequalities over a bunch of real-valued variables? – Neal Young Nov 24 '19 at 23:55