The Limits: Advice, Restriction, and P versus NP

14.1 The challenge, made explicit

The research program began with an ambitious conjecture: if computational structures have sufficiently expressive grammars, certain problems might become dramatically easier — perhaps resolvable in constant or near-constant time. A conjecture of that kind is only worth stating if it is stated against something precise. The table lists each classical boundary this book has touched, what CGT proposed against it, and what a proof would have to show.

Several rows are negative. That is the point of making the challenge explicit: a precise “no” is a scientific result, and it sharpens what the positive rows mean.

14.2 Grammars and the P/NP boundary

Let $\Pi \subseteq \{0,1\}^*$ be a decision problem, and suppose a “grammar” $\Gamma$ is attached to inputs to help decide $\Pi$. What $\Gamma$ can do depends entirely on where it comes from and how large it is.

Read against the founding conjecture, the proposition says: within the standard models, a grammar that makes an NP-complete problem fast is either an ordinary polynomial-time algorithm in disguise (case 1 — a proof of $\P = \NP$, to be judged as such), or polynomial advice (case 2 — believed impossible), or an exponential lookup table (case 3 — retrieval, not discovery), or a restriction of the problem (case 4). There is no fifth door. The ledger records the strong form of the conjecture as rejected (CGT-NEG-009); what survives is the study of which restricted classes and which preprocessing regimes allow fast resolution — the subject of the rest of the book.

14.3 Restriction: 2-SAT

Satisfiability of CNF formulas with at most two literals per clause is solvable in linear time [Aspvall et al. 1979]: each clause $(a \vee b)$ is the pair of implications $\neg a \Rightarrow b$ and $\neg b \Rightarrow a$, and the formula is satisfiable iff no variable shares a strongly connected component of this implication graph with its negation. The implication graph is a structural grammar of the formula, and the decision procedure is the SCC algorithm of Chapter 10. With three literals per clause the problem is NP-complete, and no comparable structure is known. The tractability comes from the restriction, not from having a grammar. (The large random instance below has clause-to-variable ratio $1.5$, above the satisfiability threshold of random 2-CNF, and is unsatisfiable; deciding that also takes linear time.)

import random
from cgtsdk import Cost
from cgtsdk.algorithms import brute_force_count, satisfies, two_sat

rng = random.Random(11)
agree = 0
for trial in range(300):
    n = rng.randrange(2, 13)
    clauses = [tuple(rng.choice([v, -v]) for v in rng.sample(range(1, n + 1), 2)) for _ in range(rng.randrange(1, 2 * n))]
    a = two_sat(n, clauses)
    agree += (a is not None) == (brute_force_count(n, clauses) > 0) and (a is None or satisfies(a, clauses))
print(f"2-SAT via implication-graph SCCs agrees with brute force on {agree}/300 random formulas")
c = Cost()
big = [tuple(rng.choice([v, -v]) for v in rng.sample(range(1, 100_001), 2)) for _ in range(150_000)]
print("100,000 variables, 150,000 clauses:", "satisfiable" if two_sat(100_000, big, c) else "unsatisfiable",
      f"- {c.counts['edge']} edge inspections (linear in the formula)")

2-SAT via implication-graph SCCs agrees with brute force on 300/300 random formulas
100,000 variables, 150,000 clauses: unsatisfiable - 600000 edge inspections (linear in the formula)

14.4 Solution grammars for 3-SAT

The most expressive grammar one can attach to a satisfiability instance is a grammar generating exactly its satisfying assignments — in its canonical form, a layered deterministic automaton over $\{0,1\}$, essentially an ordered binary decision diagram. Once it exists, satisfiability, model counting and many other queries are linear in its size: retrieval. This is knowledge compilation, a field that maps exactly this trade-off between the succinctness of a target representation and the queries it supports in polynomial time [Darwiche & Marquis 2002]. The question for CGT is what building it costs.

The ledger’s experiment (CGT-EXP-006) built the automaton by deduplicating residual clause sets, under the natural variable order, for random 3-CNF near the satisfiability threshold and random 2-CNF:

import random, math
from cgtsdk.algorithms import solution_automaton

rng = random.Random(6)
for label, width, ratio in (("3-CNF, m/k=4.26", 3, 4.26), ("2-CNF, m/k=1.0", 2, 1.0)):
    row = []
    for k in (8, 12, 16, 20, 24):
        sizes = []
        for _ in range(5):
            cls = [tuple((v + 1) * rng.choice([1, -1]) for v in rng.sample(range(k), width)) for _ in range(round(ratio * k))]
            sizes.append(solution_automaton(k, cls)[2])
        row.append(sorted(sizes)[2])
    print(f"{label:16s} median automaton nodes for k=8..24: {row}")

3-CNF, m/k=4.26  median automaton nodes for k=8..24: [47, 212, 875, 2835, 10855]
2-CNF, m/k=1.0   median automaton nodes for k=8..24: [36, 73, 174, 340, 1260]

The sizes grow quickly, but over this range an exponential fit and a polynomial fit of high degree describe the medians about equally well ($R^2 \approx 0.99$ and $0.98$ in the ledger’s larger run, CGT-OBS-011). The data cannot decide the asymptotics, and the book makes no asymptotic claim from them. Two things can be said. First, 2-CNF automata grow too, more slowly: 2-SAT’s linear-time algorithm does not come from a small solution grammar. Second, if a polynomial-size solution grammar could always be built in polynomial time, satisfiability would be in P (case 1 of Proposition 14.1); whatever the asymptotics of these particular automata, the construction cost is where any claim must be checked. Known exponential lower bounds for decision-diagram representations of some formulas are part of the knowledge-compilation literature; connecting them precisely to this experiment is open (CGT-OPEN-006).

14.5 Grammars whose size depends on numbers

Chapter 11’s knapsack dynamic program is a grammar of subproblems with $\Theta(nW)$ productions, where $W$ is a number in the input. It is polynomial in the value $W$ and exponential in its length $\log_2 W$. Any claim that a grammar resolves a numerical NP-hard problem “in polynomial time” must say polynomial in what: an input of length $\ell$ can encode numbers as large as $2^\ell$.

14.6 What survives

Within standard models, grammars do not change complexity classes. What this book has established instead is a set of precise local results: where a grammar’s structure is a cheap algorithm (dense addressing, compiled words, restricted classes), where it is a disguised precomputation bounded by information content, and where it is a constraint whose cost can go either way. These are the results that a “challenge to the foundations” can honestly claim at present: not a new complexity class, but a sharper map of where grammatical structure becomes computational advantage and where it provably cannot.

Report an erratum or an unclear passage in this chapter