3
$\begingroup$

It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.

  1. If implemented as an arithmetic circuit does it require $\Omega(\log L)$ depth to achieve polynomial size when $n$ is fixed or is the depth just $O(1)$?

  2. How does the depth change if $n$ changes?

  3. Is there a way to measure its bit and boolean circuit complexity?

$\endgroup$

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.