  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
$\mathrm{FP}_1$ and $\#\mathrm{P}_1$. $\mathrm{FP}_1$ includes functions
computable by a deterministic Turing machine in polynomial time, whereas
$\#\mathrm{P}_1$ encompasses functions that count the number of solutions
verifiable in polynomial time. It is widely assumed that
$\mathrm{FP}_1\neq\#\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_*$ such that for sufficiently large
$P_*\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{FP}_1\neq\#\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.
