document: Computational complexity of probabilistic disambiguation Recent models of natural language processing employ statistical reasoning for dealing with the ambiguity of formal grammars . In this approach , statistics , concerning the various linguistic phenomena of interest , are gathered from actual linguistic data and used to estimate the probabilities of the various entities that are generated by a given grammar , e.g. , derivations , parse-trees and sentences . The extension of grammars with probabilities makes it possible to state ambiguity resolution as a constrained optimization formula , which aims at maximizing the probability of some entity that the grammar generates given the input -LRB- e.g. , maximum probability parse-tree given some input sentence -RRB- . The implementation of these optimization formulae in efficient algorithms , however , does not always proceed smoothly . In this paper , we address the computational complexity of ambiguity resolution under various kinds of probabilistic models . We provide proofs that some , frequently occurring problems of ambiguity resolution are NP-complete . These problems are encountered in various applications , e.g. , language understanding for textand speech-based applications . Assuming the common model of computation , this result implies that , for many existing probabilistic models it is not possible to devise tractable algorithms for solving these optimization problems
doc_bio_tags: B I O B I O O O B I I O B I O O O O O O B I O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O