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

Since the work of Polyanskiy, Poor and Verdú 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 ${\mathrm{F}\mathrm{P}}_1$ and $\mathrm{\#}{\mathrm{P}}_1$. ${\mathrm{F}\mathrm{P}}_1$ includes functions computable by a deterministic Turing machine in polynomial time, whereas $\mathrm{\#}{\mathrm{P}}_1$ encompasses functions that count the number of solutions verifiable in polynomial time. It is widely assumed that ${\mathrm{F}\mathrm{P}}_1\mathrm{\ne }\mathrm{\#}{\mathrm{P}}_1$. It is of interest to determine the conditions under which, for a given $M\in \mathbb{N}$, where $M$ describes the precision of the deviation of $C(P,N)$, for a certain blocklength $n_M$ and a decoding error $\epsilon >0$ with $\epsilon \in \mathbb{Q}$, the following holds: $R_{n_M}(\epsilon )>C(P,N)-\frac{1}{2^M}$. It is shown that there is a polynomial-time computable $N_{\ast }$ such that for sufficiently large $P_{\ast }\in \mathbb{Q}$, the sequences $\{R_{n_M}(\epsilon ){\}}_{n_M\in \mathbb{N}}$, where each $R_{n_M}(\epsilon )$ satisfies the previous condition, cannot be computed in polynomial time if ${\mathrm{F}\mathrm{P}}_1\mathrm{\ne }\mathrm{\#}{\mathrm{P}}_1$. Hence, the complexity of computing the sequence $\{R_{n_M}(\epsilon ){\}}_{n_M\in \mathbb{N}}$ grows faster than any polynomial as $M$ increases. Consequently, it is shown that either the sequence of achievable rates $\{R_{n_M}(\epsilon ){\}}_{n_M\in \mathbb{N}}$ as a function of the blocklength, or the sequence of blocklengths $\{n_M{\}}_{M\in \mathbb{N}}$ corresponding to the achievable rates, is not a polynomial-time computable sequence.