Finite Blocklength Performance of Capacity-achieving Codes in the Light of Complexity Theory

Since the work of Polyanskiy, Poor and Verd\'u on the finite blocklength performance of capacity-achieving codes for discrete memoryless channels, many papers have attempted to find further results for more practically relevant channels. However, it seems that the complexity of computing capacity-achieving codes has not been investigated until now. We study this question for the simplest non-trivial Gaussian channels, i.e., the additive colored Gaussian noise channel. To assess the computational complexity, we consider the classes FP₁ and #P₁. FP₁ includes functions computable by a deterministic Turing machine in polynomial time, whereas #P₁ encompasses functions that count the number of solutions verifiable in polynomial time. It is widely assumed that FP₁≠#P₁. It is of interest to determine the conditions under which, for a given M ∈ N, where M describes the precision of the deviation of $C(P,N)$, for a certain blocklength nM and a decoding error ε > 0 with ε, the following holds: RnM(ε)>C(P,N)-1/2M. It is shown that there is a polynomial-time computable N_* such that for sufficiently large P_*, the sequences (ε)_nM, where each RnM(ε) satisfies the previous condition, cannot be computed in polynomial time if FP₁≠#P₁. Hence, the complexity of computing the sequence (ε) grows faster than any polynomial as M increases. Consequently, it is shown that either the sequence of achievable rates (ε) as a function of the blocklength, or the sequence of blocklengths corresponding to the achievable rates, is not a polynomial-time computable sequence.