Easy and Hard Constraint Ranking in OT: Algorithms and Complexity

Jason EisnerarXiv 2001 · OpenReview

Abstract: We consider the problem of ranking a set of Optimality Theory (OT) constraints in a manner consistent with data. We speed up Tesar and Smolensky's Recursive Constraint Demotion (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.

Introduction

In Optimality Theory (OT), a grammar is defined by a set of universal constraints. The learning task involves finding a specific ranking of these constraints such that observed grammatical forms are "optimal"—meaning they violate high-ranked constraints less than any other possible candidate. While OT has become a dominant framework in linguistics, Jason Eisner’s research (presented at SIGPHON 2000) provides a rigorous examination of the computational "bill" associated with this framework. This paper serves as a complexity warning, demonstrating that while basic ranking tasks can be optimized, realistic learning scenarios are fundamentally more expensive than traditional derivational phonology.

Algorithmic Optimization: The "Easy" Part

The paper first addresses the efficiency of existing ranking algorithms, specifically Tesar and Smolensky’s Recursive Constraint Demotion (RCD). Eisner re-imagines RCD as a version of Topological Sort on a directed hypergraph.

By applying standard computer science bookkeeping—such as maintaining parent counts and adjacency lists—Eisner reduces the runtime of the ranking step from $O(Mn^2)$ to $O(Mn)$, where $n$ is the number of constraints and $M$ is the number of data pairs. This linear speedup represents the most efficient possible implementation for finding a ranking where an attested form $x_i$ beats a specific competitor $y_i$.

The Complexity of Realistic OT: The "Hard" Part

The "Hard" portion of the paper’s title refers to the transition from toy examples to realistic linguistic data. Eisner uses reductions from classic problems like Hamiltonian Path and Boolean Satisfiability (SAT) to prove several hardness results:

1. The "All Competitors" Trap

In simplified models, we compare a winner to a few hand-picked losers. In reality, a winner must beat all possible competitors, which can be an infinite set. Eisner proves that checking if a ranking is consistent against all competitors is coNP-complete.

2. Hidden Structure and Surface Sets

Learners rarely observe the full internal structure of words (e.g., prosodic trees or underlying morphemes). When dealing with incompletely observed forms (surface sets), the ranking problem becomes $\Sigma^p_2$-complete. This high level of complexity suggests that natural OT learning is significantly more difficult than previously assumed.

3. Generation Complexity

Even the task of generation—producing a word from a known grammar—is shown to be OptP-complete. This class is associated with difficult optimization problems like the Traveling Salesperson Problem, indicating that OT generation is inherently harder than the polynomial-time generation found in rule-based systems.

OT vs. Derivational Theories

A key insight of the paper is the formal asymmetry between OT and derivational phonology. In derivational theories (where rules are applied sequentially, $A \to B \to C$), generation is in P (polynomial time). Ranking or rule discovery is NP-complete. In contrast, OT’s reliance on global optimization across a candidate set pushes its complexity into higher tiers of the polynomial hierarchy, such as OptP and $\Sigma^p_2$.

Conclusion

Eisner’s work establishes that the computational cost of OT is substantial. While specific algorithmic tricks can optimize basic ranking, the general problems of generation and learning from surface forms are intractable in the worst case. These results suggest that if OT is a cognitively plausible model, there must be specific restrictions on the nature of constraints or the structure of the candidate generator that prevent these hard cases from occurring in natural language. Future work remains to identify whether heuristics, randomized algorithms, or parameterized complexity can bridge the gap between these theoretical bounds and the apparent ease of human language acquisition.

Summary updated

Abstract

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.
BibTeX
@misc{eisner2001easy,
  author = {Jason Eisner},
  title = {{Easy and Hard Constraint Ranking in OT: Algorithms and Complexity}},
  year = {2001},
  eprint = {cs/0102019},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cs/0102019},
}

Loading related content...

Figure