  This paper studies the computational complexity of disambiguation under
probabilistic tree-grammars and context-free grammars. It presents a proof that
the following problems are NP-hard: computing the Most Probable Parse (MPP)
from a sentence or from a word-graph, and computing the Most Probable Sentence
(MPS) from a word-graph. The NP-hardness of computing the MPS from a word-graph
also holds for Stochastic Context-Free Grammars. Consequently, the existence of
deterministic polynomial-time algorithms for solving these disambiguation
problems is a highly improbable event.
