Manuscript Oai279-A@1 · Oai279-A.tex · section · a1abc73f

The quantifiers matter

Stage 3: an existence theorem, a generator, and one circuit › The quantifiers matter · lines 1331–1350

Back to manuscript

For any fixed , a circuit that writes its already known factorization is easy to specify. That establishes only a statement with the weak quantifier pattern

It does not establish a polynomial-time length generator whose output handles every of that length.

Similarly, any finite collection of factorizations can be compiled into a finite reversible lookup table. Its gate count depends on the number of rows. Treating that row count as a constant while claiming an unbounded-input theorem would change the resource model.

The local circuit avoids a vacuous single-answer demonstration by handling every , but it does not pretend that this finite improvement proves the stronger uniform quantifier.

Displayed formulas in this passage

  • unlabeled · line 1336