Easy and Hard Constraint Ranking in OT: Algorithms and Complexity
<|reference_start|>Easy and Hard Constraint Ranking in OT: Algorithms and Complexity: We consider the problem of ranking a set of OT constraints in a manner consistent with data.   We speed up Tesar and Smolensky's RCD algorithm to be linear on the number of constraints. This finds a ranking so each attested form x_i beats or ties a particular competitor y_i. We also generalize RCD so each x_i beats or ties all possible competitors.   Alas, this more realistic version of learning has no polynomial algorithm unless P=NP! Indeed, not even generation does. So one cannot improve qualitatively upon brute force:   Merely checking that a single (given) ranking is consistent with given forms is coNP-complete if the surface forms are fully observed and Delta_2^p-complete if not. Indeed, OT generation is OptP-complete. As for ranking, determining whether any consistent ranking exists is coNP-hard (but in Delta_2^p) if the forms are fully observed, and Sigma_2^p-complete if not.   Finally, we show that generation and ranking are easier in derivational theories: in P, and NP-complete.<|reference_end|>
@article{eisner2001easy,
    title={Easy and Hard Constraint Ranking in OT: Algorithms and Complexity},
    author={Jason Eisner (Dept. of Computer Science / University of Rochester)},
    journal={Jason Eisner, Lauri Karttunen and Alain Theriault (eds.),
  Finite-State Phonology: Proceedings of the 5th Workshop of the ACL Special
  Interest Group in Computational Phonology (SIGPHON), pp. 22-33. Luxembourg,
  August 2000},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0102019},
    primaryClass={cs.CL cs.CC}
}