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 #P-1-complete. This means that it is even more complex than problems that are NP1-complete. Additionally, it is shown that computing the capacity-achieving input p.s.d. is also #P-1-complete. Furthermore, under the widely accepted assumption that FP1 not equal #P-1, 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.