1
$\begingroup$

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)?

Related:https://mathoverflow.net/questions/343396/quantifier-elimination-with-no-free-variables-and-real-polyhedral-inequalities

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.

$\endgroup$
1
  • 1
    $\begingroup$ "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? $\endgroup$ – Neal Young Nov 24 '19 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.