4

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?

Turbo
  • 12,812
  • 1
  • 19
  • 68

1 Answers1

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.

Community
  • 1