tech,151E061004,bq 
are of considerable importance to
<term>

Statistical Machine Translation ( SMT )

</term>
but which have not been addressed

#9937
In this paper we study a set of problems that are of considerable importance toStatistical Machine Translation ( SMT ) but which have not been addressed satisfactorily by the SMT research community. 
other,301E061004,bq 
been addressed satisfactorily by the
<term>

SMT research community

</term>
. Over the last decade , a variety

#9952
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 theSMT research community. 
tech,82E061004,bq 
Over the last decade , a variety of
<term>

SMT algorithms

</term>
have been built and empirically tested

#9964
Over the last decade, a variety ofSMT algorithms have been built and empirically tested whereas little is known about the computational complexity of some of the fundamental problems of SMT. 
other,222E061004,bq 
whereas little is known about the
<term>

computational complexity

</term>
of some of the fundamental problems

#9978
Over the last decade, a variety of SMT algorithms have been built and empirically tested whereas little is known about thecomputational complexity of some of the fundamental problems of SMT. 
tech,312E061004,bq 
some of the fundamental problems of
<term>

SMT

</term>
. Our work aims at providing useful

#9987
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 ofSMT. 
other,103E061004,bq 
providing useful insights into the the
<term>

computational complexity

</term>
of those problems . We prove that

#9999
Our work aims at providing useful insights into the thecomputational complexity of those problems. 
tool,44E061004,bq 
those problems . We prove that while
<term>

IBM Models 12

</term>
are conceptually and computationally

#10009
We prove that whileIBM Models 12 are conceptually and computationally simple, computations involving the higher (and more useful) models are hard. 
model,224E061004,bq 
involving the higher ( and more useful )
<term>

models

</term>
are
<term>
hard
</term>
. Since it is

#10027
We prove that while IBM Models 12 are conceptually and computationally simple, computations involving the higher (and more useful)models are hard. 
other,244E061004,bq 
more useful )
<term>
models
</term>
are
<term>

hard

</term>
. Since it is unlikely that there

#10029
We prove that while IBM Models 12 are conceptually and computationally simple, computations involving the higher (and more useful) models arehard. 
other,85E061004,bq 
it is unlikely that there exists a
<term>

polynomial time solution

</term>
for any of these
<term>
hard problems

#10039
Since it is unlikely that there exists apolynomial 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. 
other,155E061004,bq 
time solution
</term>
for any of these
<term>

hard problems

</term>
( unless
<term>
P = NP
</term>
and
<term>

#10046
Since it is unlikely that there exists a polynomial time solution for any of thesehard problems (unless P = NP and P#P = P), our results highlight and justify the need for developing polynomial time approximations for these computations. 
other,195E061004,bq 
<term>
hard problems
</term>
( unless
<term>

P = NP

</term>
and
<term>
P #P = P
</term>
) , our results

#10050
Since it is unlikely that there exists a polynomial time solution for any of these hard problems (unlessP = NP and P#P = P), our results highlight and justify the need for developing polynomial time approximations for these computations. 
other,235E061004,bq 
</term>
( unless
<term>
P = NP
</term>
and
<term>

P #P = P

</term>
) , our results highlight and justify

#10054
Since it is unlikely that there exists a polynomial time solution for any of these hard problems (unless P = NP andP #P = P), our results highlight and justify the need for developing polynomial time approximations for these computations. 
other,385E061004,bq 
and justify the need for developing
<term>

polynomial time approximations

</term>
for these computations . We also

#10069
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 developingpolynomial time approximations for these computations. 
other,96E061004,bq 
some practical ways of dealing with
<term>

complexity

</term>
. In this paper a novel solution

#10085
We also discuss some practical ways of dealing withcomplexity. 