Type-Logical Grammars Are NP-Complete — and That Might Be Exactly the Right Complexity for Human Language

A proof that type-logical grammars with standard structural rules hit NP-completeness, plus a stronger result: first-order linear logic captures exactly the non-deterministic linear-time string languages.

Imagine you're playing Scrabble, but instead of just checking whether a word is in the dictionary, your scoring system has to verify that every tile placement follows a chain of logical deductions — each tile justified by a rule, each rule consuming exactly one resource. That's the computational texture of type-logical grammars: parsing isn't pattern-matching, it's proof-search in a resource-sensitive logic. The question this paper settles is: how hard is that search, and does it correspond to anything natural? The committed claim: type-logical grammars equipped with the standard structural rules (product, associativity, extraction, infixation) have an NP-complete fixed recognition problem. This adapts a construction from Pshenitsyn (2025), who showed that first-order linear logic grammars are closed under intersection — which immediately rules them out as semilinear or mildly context-sensitive. Moot goes further, showing these grammars can simulate the quasi-linear grammars of Book & Greibach (1970), which recognize exactly the languages decided in non-deterministic linear time (NLIN, or NSPACE(n)). The architecture here is proof-theoretic, not algorithmic in the usual sense. Type-logical grammars assign logical formulas (types) to words; a sentence is grammatical if you can derive a proof that the types compose to a designated goal type. The logic in play is first-order multiplicative linear logic — no contraction, no weakening, every resource used exactly once. The structural rules (associativity, extraction, infixation) add controlled flexibility. The key construction encodes NP-hard problems as recognition tasks within this framework, leveraging the intersection closure result as a stepping stone. Where does this sit on the ladder? The standard complexity benchmark for natural language formalisms is LOGCFL (the languages recognized by log-space auxiliary pushdown automata), which captures context-free and mildly context-sensitive grammars. This paper argues NLIN is the right upper bound on time complexity, just as LOGCFL bounds space complexity. The result positions first-order linear logic strictly above the mildly context-sensitive hierarchy — not as a failure, but as a feature: human language may genuinely need this much power, and NLIN is a principled place to draw the line. The integrity of the result rests on mathematical proof, not simulation or experiment. The NP-completeness result is a reduction; the NLIN simulation result is a direct construction. There's no cherry-picking risk in the usual empirical sense — the question is whether the proof is correct and the construction valid. The reliance on Pshenitsyn (2025) for the intersection closure lemma means the full result chain depends on that prior work's correctness. The milestone question is conceptual rather than numeric. The paper proposes NLIN as the canonical complexity class for natural language time complexity. The next concrete step is whether practical parsing algorithms can be designed that exploit this characterization — can you build parsers for NLIN-complete grammars that run efficiently on typical natural language inputs (which are far from worst-case)? The gap between worst-case NP-completeness and average-case tractability is where the action is. The obvious experiment not run: empirical validation on real natural language corpora. Can you take a type-logical grammar with these structural rules, parse actual sentences from a treebank, and measure whether the NP-complete worst case ever bites in practice? Moot is a computational linguist who has built such parsers before (Grail), so this is likely (c) — saved for the next paper, where the theoretical ceiling established here becomes the backdrop for practical parsing work.