NP Witness as Canonical Address

An NP witness = τ-address w with unique NF decomposition (A,B,C,D). The ABCD coordinates structure the witness space: search the 4-component coordinate space instead of arbitrary bitstrings. E₂-native definition.

NP Witness as Canonical Address

Summary

An NP witness = τ-address w with unique NF decomposition (A,B,C,D). The ABCD coordinates structure the witness space: search the 4-component coordinate space instead of arbitrary bitstrings. E₂-native definition.

Statement

\label{def:np-witness-canonical-address}
Let $\Pi$ be a decision problem computable on the TTM, and let $x$
be a $\tau$-address representing a ``yes'' instance of~$\Pi$.
An \textbf{NP witness for $x$ at primorial depth $k$} is a
$\tau$-address $w \in \mathbb{Z}/\operatorname{Prim}(k)\mathbb{Z}$
such that the TTM verifier $V$ accepts $(x, w)$ in at most $T(|x|)$
steps, where $T$ is a fixed polynomial.
The \textbf{witness space at depth $k$} is
\[
W(x, k) \;=\; \bigl\{\, w \in \mathbb{Z}/\operatorname{Prim}(k)\mathbb{Z}
  \;\big|\; V(x, w) \text{ accepts} \,\bigr\}.
\]

Proof / Justification

This item is definitional. No manuscript proof is required.

Source Context

• Registry source: book-03.jsonl line 152
• Manuscript source: 2nd-edition/book-iii-categorical-spectrum/02_mainmatter/part09/ch57-witness-search-as-address-resolution.tex lines 47-60

Lean / Formalization Notes

• Formalization: formalized
• Module: TauLib.BookIII.Computation.WitnessSearch
• Name: witness_check

Dependencies

• Canonical: III.D51, III.T10, III.D20

Related Results

Generated by later projection phases.

Related Publications

Generated by later projection phases.

Revision Notes

• 2026-04-24: Initial pilot migration.