Communications in Information and Systems

Volume 17 (2017)

Number 4

PSPACE hardness of approximating the capacity of time-invariant Markov channels with perfect feedback

Pages: 249 – 256



Mukul Agarwal (Dept. of Electrical and Computer Engineering, Boston University, Boston, Massachusetts, U.S.A.)


It is proved that approximating the capacity of a time-invariant Markov channel with perfect feedback is PSPACE hard.

Published 14 March 2018