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 FP1 and #P1. FP1 includes functions computable by a deterministic Turing machine in polynomial time, whereas #P1 encompasses functions that count the number of solutions verifiable in polynomial time. It is widely assumed that FP1≠#P1. It is of interest to determine the conditions under which, for a given M∈ℕ, 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)−12M. It is shown that there is a polynomial-time computable N∗ such that for sufficiently large P∗∈ℚ, the sequences {RnM(ϵ)}nM∈ℕ, where each RnM(ϵ) satisfies the previous condition, cannot be computed in polynomial time if FP1≠#P1. Hence, the complexity of computing the sequence {RnM(ϵ)}nM∈ℕ grows faster than any polynomial as M increases. Consequently, it is shown that either the sequence of achievable rates {RnM(ϵ)}nM∈ℕ as a function of the blocklength, or the sequence of blocklengths {nM}M∈ℕ corresponding to the achievable rates, is not a polynomial-time computable sequence.