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

DOI: https://dx.doi.org/10.4310/CIS.2017.v17.n4.a3

Author

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

Abstract

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

Published 14 March 2018