-
A Simple Proof That Optimality Theory Is Computationally Intractable
- Linguistic Inquiry
- The MIT Press
- Volume 37, Number 2, Spring 2006
- pp. 271-275
- Article
- Additional Information
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).