期刊名称：Conference on European Chapter of the Association for Computational Linguistics (EACL)
出版年度：2006
卷号：2006
出版社：ACL Anthology
摘要：In this paper we study a set of problems
that are of considerable importance
to Statistical Machine Translation (SMT)
but which have not been addressed satisfactorily
by the SMT research community.
Over the last decade, a variety of SMT
algorithms have been built and empirically
tested whereas little is known about
the computational complexity of some of
the fundamental problems of SMT. Our
work aims at providing useful insights into
the the computational complexity of those
problems. We prove that while IBM Models
1-2 are conceptually and computationally
simple, computations involving the
higher (and more useful) models are hard.
Since it is unlikely that there exists a polynomial
time solution for any of these hard
problems (unless P = NP and P#P =
P), our results highlight and justify the
need for developing polynomial time approximations
for these computations. We
also discuss some practical ways of dealing
with complexity.
