Quarterly (winter, spring, summer, fall)
224 pp. per issue
6 3/4 x 9 1/4
ISSN
0024-3892
E-ISSN
1530-9150
2014 Impact factor:
1.71

Linguistic Inquiry

Spring 2006, Vol. 37, No. 2, Pages 271-275
(doi: 10.1162/ling.2006.37.2.271)
© 2006 Massachusetts Institute of Technology
A Simple Proof That Optimality Theory Is Computationally Intractable
Article PDF (266.29 KB)
Abstract

Adapting arguments from Eisner 1997, 2000, this remark provides a simple proof that the generation problem for Optimality Theory (Prince and Smolensky 2004) is NP-hard. The proof needs only the binary evaluation of constraints and uses only constraints generally employed in the Optimality Theory literature. In contrast, rule-based derivational systems are easily computable, belonging to the class of polynomialtime algorithms, P (Eisner 2000).