18.2 The quantified model boundary
On this page · Permalink · Source line 539
The same map \(\Phi\) here serves all predicates on a fixed witness space. It is linear, multiplicative, and retains every primitive witness indicator. Under exactly these assumptions, a polynomial-dimensional summary is impossible as \(m\) grows.
An arbitrary algorithm is not required to satisfy these hypotheses. It may use nonlinear encodings, syntax-dependent operations, changing spaces, or succinct descriptions inside an exponentially large algebra. A description of the algebra and a description of one relevant element can be much shorter than a full coordinate listing.
No dimension-to-circuit inference
The theorem excludes a fixed faithful linear multiplicative compression of the full witness algebra into fewer than \(2^m\) dimensions. It does not exclude every polynomial-time decision procedure, does not prove \(P\ne NP\), and does not justify treating the algebra's dimension as the circuit cost of an individual decision function.
The finite scalar controls enumerate 256 linear maps from a two-point witness algebra to \(\mathrm{GF}(16)\), 65,536 maps for four points, and 256 maps from an eight-point algebra to \({\mathbb F_2}\). The respective counts of unital algebra homomorphisms are two, four, and eight, matching the evaluation classification. The all-size result rests on the proof above.