Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a deterministic algorithm that runs in $O((nk)^{ck})$ time for some $c>0$. What is the space complexity of the algorithm? Does it run in polynomial space?


According to this answer, "the space complexity of the algorithm" is polynomial when ​ 2.5 < c .
That answer does not indicate the polynomial's exponent.

  • $\begingroup$ Lenstra's alg is just dynamic programing memoization will make it poly space $\endgroup$ – 1.. Mar 30 '17 at 17:41
  • $\begingroup$ I should not said memoization but said reusing same space $\endgroup$ – 1.. Apr 1 '17 at 1:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.