TY - JOUR

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

AU - Boche, Holger

AU - Grigorescu, Andrea

AU - Schaefer, Rafael F.

AU - Poor, H. Vincent

N1 - Publisher Copyright:
© 1972-2012 IEEE.

PY - 2024

Y1 - 2024

N2 - This paper explores the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving power spectral density (p.s.d.). The study reveals that when the noise p.s.d. is a strictly positive computable continuous function, computing the capacity of the band-limited ACGN channel becomes a #mathrm {P}_{1} -complete problem within the set of polynomial time computable noise p.s.d.s, meaning that it is even more complex than problems that are NP1-complete. Additionally, it is shown that computing the capacity-achieving distribution is also #mathrm {P}_{1} -complete. Furthermore, under the widely accepted assumption that mathrm {FP}_{1} neq #mathrm {P}_{1} , this has two significant implications for the ACGN channel. The first implication is the existence of a polynomial time computable noise p.s.d. for which the computation of the corresponding ACGN capacity cannot be performed in polynomial time, i.e., the number of computational steps on a Turing machine grows faster than all polynomials. The second is the existence of a polynomial time computable noise p.s.d. for which determining the corresponding ACGN's capacity-achieving p.s.d. cannot be done within polynomial time. This implies that either the sequence of achievable rates with guaranteed distance to capacity is not polynomial time computable, or the corresponding blocklength sequence is not polynomial time computable.

AB - This paper explores the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving power spectral density (p.s.d.). The study reveals that when the noise p.s.d. is a strictly positive computable continuous function, computing the capacity of the band-limited ACGN channel becomes a #mathrm {P}_{1} -complete problem within the set of polynomial time computable noise p.s.d.s, meaning that it is even more complex than problems that are NP1-complete. Additionally, it is shown that computing the capacity-achieving distribution is also #mathrm {P}_{1} -complete. Furthermore, under the widely accepted assumption that mathrm {FP}_{1} neq #mathrm {P}_{1} , this has two significant implications for the ACGN channel. The first implication is the existence of a polynomial time computable noise p.s.d. for which the computation of the corresponding ACGN capacity cannot be performed in polynomial time, i.e., the number of computational steps on a Turing machine grows faster than all polynomials. The second is the existence of a polynomial time computable noise p.s.d. for which determining the corresponding ACGN's capacity-achieving p.s.d. cannot be done within polynomial time. This implies that either the sequence of achievable rates with guaranteed distance to capacity is not polynomial time computable, or the corresponding blocklength sequence is not polynomial time computable.

KW - Channel capacity

KW - Gaussian channels

KW - capacity achieving codes

KW - computational complexity

KW - finite blocklength performance

UR - http://www.scopus.com/inward/record.url?scp=85189328836&partnerID=8YFLogxK

U2 - 10.1109/TCOMM.2024.3381705

DO - 10.1109/TCOMM.2024.3381705

M3 - Article

AN - SCOPUS:85189328836

SN - 0090-6778

VL - 72

SP - 4844

EP - 4856

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

IS - 8

ER -