Evaluating the Complexity of Optimality Theory

Abstract

Idsardi (2006) claims that Optimality Theory (OT; Prince and Smolensky 1993, 2004) is “in general computationally intractable” on the basis of a proof adapted from Eisner 1997a. We take issue with this conclusion on two grounds. First, the intractability result holds only in cases where the constraint set is not fixed in advance (contra usual definitions of OT), and second, the result crucially depends on a particular representation of OT grammars. We show that there is an alternative representation of OT grammars that allows for efficient computation of optimal surface forms and provides deeper insight into the sources of complexity of OT. We conclude that it is a mistake to reject OT on the grounds that it is computationally intractable.