[Author Login]
Title:Is OT NP-hard?
Authors:Andras Kornai
Abstract:Idsardi (2006) offers a streamlined proof of the thesis that the generation problem of OT is NP-hard. This is a welcome attempt to shed light on this complex matter, but, as we shall demonstrate here, it falls short in justifying the constraints employed in setting up the reduction of OT generation to a known NP-hard problem. The problem is that for a successful encoding dissimilation constraints over an unbounded domain would be required, but these, as we argue, are unattested in the phonologies of natural languages -- the attested constraints (Lyman's Law, Grassman's Law, etc) pertain to a finite (and very small) inventory, namely the nodes in feature geometry.

Type:Paper/tech report
Area/Keywords:Formal Analysis,Computation
Article:Version 1