Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian Channels

This paper investigates the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving input power spectral density (p.s.d.). A band-limited polynomial time computable continuous and strictly positive noise p.s.d. is constructed for the ACGN channel such that the computation of its corresponding capacity is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\# \mathrm{P}_{1}$</tex>-complete. This means that it is even more complex than problems that are <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{NP}_{1}$</tex>-complete. Additionally, it is shown that computing the capacity-achieving input p.s.d. is also <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\# \mathrm{P}_{1}$</tex>-complete. Furthermore, under the widely accepted assumption that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\text{FP}_{1}\neq\# \mathrm{P}_{1}$</tex>, there are two significant implications for the ACGN channel. First, there exists a polynomial time computable noise p.s.d. for which computing its capacity is not polynomial-time feasible, meaning the number of computational steps on a Turing Machine grows faster than any polynomial. Second, there is a polynomial time computable noise p.s.d. where determining its capacity-achieving input p.s.d. is also not achievable in polynomial time.