Communications in Information and Systems
Volume 17 (2017)
PSPACE hardness of approximating the capacity of time-invariant Markov channels with perfect feedback
Pages: 249 – 256
It is proved that approximating the capacity of a time-invariant Markov channel with perfect feedback is PSPACE hard.