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 $k^{O(k)}\mathsf{poly(nL)})$ time for some $c>0$ where $L$ is number of bits to represent the problem.

What is the space complexity of the algorithm? Does it run in $\mathsf{poly}(nk\log L)$ space?


1 Answer 1


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.


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.