Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian Channels
Holger Boche, Andrea Grigorescu, Rafael F. Schaefer, H. Vincent Poor · 2024
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$\# \mathrm{P}_{1}$-complete. This means that it is even more complex than problems that are$\text{NP}_{1}$-complete. Additionally, it is shown that computing the capacity-achieving input p.s.d. is also$\# \mathrm{P}_{1}$-complete. Furthermore, under the widely accepted assumption that$\text{FP}_{1} eq\# \mathrm{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.