When designing formalisms to model natural language, computer scientists and linguists face a fundamental tension between expressiveness and computational efficiency. Simple models like Context-Free Grammars (CFGs) offer highly efficient polynomial-time parsing algorithms, but they fail to naturally capture the rich, non-local dependencies, agreement rules, and structural flexibility inherent in human speech and text.
To bridge this gap, researchers introduced advanced grammar formalisms equipped with features, constraints, and unification mechanisms. However, this added expressive power introduces a severe mathematical penalty: it frequently elevates basic linguistic tasks—such as determining if a sentence is grammatical (recognition) or turning a semantic idea into words (generation)—into NP-complete, NP-hard, or even exponentially harder problems.
Understanding why these formalisms break down computationally requires looking at how linguistic constraints inadvertently simulate hard mathematical problems.
Why Recognition and Parsing Explode
The goal of a parser is to take a string of words and determine its structural derivation according to a set of grammatical rules. In simple grammars, this is a matter of local phrase-structure matching. But when a grammar framework introduces global features or long-distance dependencies, the parser must ensure that features match across distant parts of a sentence.
This capacity to pass and validate features across arbitrary distances allows expressive grammars to act as general-purpose computers. In a landmark survey, On the Mathematical Properties of Linguistic Theories, Perrault demonstrated that linguistic formalisms capable of encoding boolean satisfiability (SAT) problems inherently result in NP-complete recognition tasks. When a grammar can enforce complex, interlocking constraints, verifying that a sentence is valid becomes mathematically identical to finding a satisfying assignment for a logic formula.
This vulnerability appears across a wide variety of syntactic frameworks:
- Lexical Functional Grammar (LFG): By separating constituent structures from functional structures (f-structures) that handle agreement and uniqueness constraints, LFG allows for highly precise linguistic descriptions. However, [Eisele] et al. noted in A Lexical Functional Grammar System in Prolog that this reliance on constraint unification makes LFG recognition fundamentally NP-complete, limiting its out-of-the-box scalability for large-scale processing.
- Generalized Phrase Structure Grammar (GPSG): GPSG was initially thought to be computationally efficient because it is weakly equivalent to context-free grammars. However, Ristad debunked this assumption in Computational Complexity of Current GPSG Theory, proving that universal recognition for GPSG is actually Exp-Poly hard. The underlying mechanism driving this extreme complexity is the interplay between null-transitions and universal feature instantiation, which effectively allows the grammar to simulate complex machine memory.
- Feature-Based and Categorial Grammars: Søgaard proved in Logical investigations on the adequacy of certain feature-based theories of natural language that the universal recognition problem for general feature-based formalisms is NP-complete. Similarly, when formalisms introduce flexible extraction rules—such as Semidirectional Lambek Grammars—the parsing problem becomes NP-complete. Dorre demonstrated this in Parsing with Semidirectional Lambek Grammar is NP-Complete by using a reduction from the 3-Partition Problem, showing that arranging linguistic elements under these rules mirrors the difficulty of perfectly packing bins.
- Synchronous Context-Free Grammars (SCFGs): Even when structured models are applied to machine translation to map structures between two languages, tractability is not guaranteed. As shown by [Satta] et al. in Some Computational Complexity Results for Synchronous Context-Free Grammars, the membership problem for SCFGs (checking if a pair of strings can be generated together) is NP-hard, exhibiting worst-case exponential time complexity.
The Combinatorial Explosion of Generation
Natural Language Generation (NLG)—specifically the phase known as surface realization—faces the inverse problem of parsing. Given an input semantic representation (often a "flat" bag of meanings without a predefined order), the generator must select the appropriate words and arrange them into a grammatically valid string.
This process triggers a massive combinatorial explosion. Because flat semantics do not dictate word order, a generator must evaluate an exponential number of word permutations.
[Koller] et al. proved in Generation as Dependency Parsing that surface realization from flat semantics is NP-complete even when using a fixed grammar. Without structural clues, traditional chart-based generators frequently hit exponential walls and time out. This issue is compounded when using highly expressive grammar formalisms. For instance, [Gardent] et al. explained in RTG based surface realisation for TAG that Feature-Based Lexicalized Tree Adjoining Grammars (FTAGs) lead to NP-complete surface realization because of the sheer volume of structural combinations that must be explored to satisfy both semantic and syntactic constraints.
This generation bottleneck manifests across multiple paradigms:
- Shake-and-Bake Machine Translation: In this paradigm, translation is treated as a generation task from a bag of lexical items. Brew proved in Letting the Cat Out of the Bag: Generation for Shake-and-Bake MT that this problem is NP-complete, making general-purpose, efficient algorithms for the task highly unlikely.
- M-Grammars and Interaction Grammars: Whether interpreting translation formalisms as attribute grammars (Rous in Computational Aspects of M-grammars) or utilizing polarized features to handle underspecification (Perrier in Interaction Grammars), the underlying logic remains NP-hard or NP-complete.
- Integrated Generation: If a system attempts to simultaneously determine what to say (content selection) and how to say it (surface realization), the search space expands dramatically. As [Engonopoulos] et al. demonstrated in Integrated sentence generation using charts, integrated natural language generation is fundamentally NP-complete, causing chart-based methods to experience severe slowdowns as semantic inputs grow.
Intractability in Phonology and Constraint Optimization
The curse of computational hardness is not unique to syntax and semantics; it also emerges in phonology, where underlying mental representations of words are transformed into surface pronunciations.
In Optimality Theory, language rules are replaced by a system of universal, competing constraints. To generate a surface form, a system must evaluate an infinite candidate pool of pronunciations against a ranked hierarchy of constraints. In Efficient Generation in Primitive Optimality Theory, Eisner demonstrated that finding the optimal surface form under these conditions is NP-complete. Even though human phonology feels intuitive and rapid, the mathematical reality of resolving overlapping "implication" and "clash" rules creates an intractable search space in the worst case.
A similar issue occurs when formalizing the linguistic "elsewhere condition"—the rule that specific morphological or phonological exceptions override general defaults. [Penn] et al. showed in Default Finite State Machines and Finite State Phonology that baking these priority-based conditions directly into a machine's native logic transforms generation into an NP-complete task, introducing severe scalability risks.
Designing Around Intractability
Given that these core linguistic problems are mathematically intractable in the worst case, how do computational systems manage to function at all? The field has evolved by finding ways to bypass these theoretical upper bounds through three primary strategies:
- Isolating Tractable Subsets: Instead of using a fully expressive grammar, researchers look for mathematical "sweet spots." For example, while general feature-based grammars are NP-complete, Søgaard proved that strongly monotonic hybrid grammars remain solvable in polynomial time and are learnable from positive data.
- Reframing the Search Space: Sometimes, an intractable problem can be mapped onto a different domain where advanced optimization tools exist. [Koller] et al. bypassed the NP-completeness of surface realization by encoding Tree-Adjoining Grammar generation into a Topological Dependency Grammar. This allowed them to use constraint-programming techniques to prune the search space early, achieving near-polynomial runtimes in practice.
- Packed and Factored Representations: Rather than evaluating combinations independently, modern algorithms use sharing and packing to compress the search space. [Gardent] et al. achieved this by converting TAGs into Regular Tree Grammars (RTGs) and using an Earley-style parsing chart to minimize space requirements. Similarly, in phonology, Eisner demonstrated that using "factored automata" to represent constraints can yield a 100-fold speedup, making generation practically feasible despite its underlying NP-complete nature.
Key Foundational Work
Computational Complexity and Lexical Functional Grammar (1981) — contributed 2 concept elements to this direction.
On the Mathematical Properties of Linguistic Theories (1983) — contributed 1 concept elements to this direction.