Linguistic Inquiry
Spring 2006, Vol. 37, No. 2, Pages 271-275
(doi: 10.1162/ling.2006.37.2.271)
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).