We know $$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$ $$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$ is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference).

What is the complexity of $$\forall\bf y\in\mathbb Z^n\times\mathbb R^a:K\bf y\leq b$$ $$\exists\bf x\in\mathbb Z^m\times\mathbb R^b:A\bf x + B\bf y\leq c$$ where $n,m$ are fixed?

  1. Is it still $2^{\mathsf{poly}(m+n)}\mathsf{poly}(mnab)$?

  2. At least when $n=0$ is it $2^{\mathsf{poly}(m)}\mathsf{poly}(mab)$?


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.