What does binary-encoding length means? For instance if my theorem says "An algorithm solves in time which is polynomial in n and in the binary-encoding length $<l,u,b,w>$ of the rest of the data, the following n-fold integer programming problem ..." When is the binary encoding length useful for and what do the parameters $<l,u,b,w>$ mean?
2026-04-04 08:06:24.1775289984
Binary enconding length
90 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Just a wild guess, but it probably means what it says: the length of a bitstring encoding (in some reasonable manner) the parameters $l$, $u$, $b$ and $w$.
That's because, presumably, the algorithm needs to at least read those parameters from it input, and that's going to take at least $O(k)$ time, where $k$ is the length of the input string encoding them. More generally, for most standard models of computations, the time needed for basic operations like adding or multiplying two binary numbers is also a polynomial function of their length, thus introducing a factor polynomial in the length of the input and/or any internal state variables into the runtime of pretty much all algorithms.
(Note that there are models of computation, such as the transdichotomous model, in which elementary arithmetic operations on "reasonably sized" numbers take only constant time. Such models are in some ways closer to reality, since real computers typically do support constant-time operations on variables that fit into a single CPU register.)