On the encoding complexity of scalar quantizers
Dennis Hui, David L. Neuhoff · 2002
It is shown that as rate increases the problem of asymptotically optimal scalar quantization has polynomial-time (or space) encoding complexity if the distribution function corresponding to the one-third power of the source density is polynomial-time (or space) computable in the Turing sense.