  We propose two modified versions of the classical gradient ascent method to
compute the capacity of finite-state channels with Markovian inputs. For the
case that the channel mutual information is strongly concave in a parameter
taking values in a compact convex subset of some Euclidean space, our first
algorithm proves to achieve polynomial accuracy in polynomial time and,
moreover, for some special families of finite-state channels our algorithm can
achieve exponential accuracy in polynomial time under some technical
conditions. For the case that the channel mutual information may not be
strongly concave, our second algorithm proves to be at least locally
convergent.
