Exact Semantic Carriers for Structured Physical Systems

Abstract

Exact search states may be individuated by syntactic history or by a smaller carrier preserving exact continuation semantics. We give a sufficient traversal criterion for deterministic polynomial-time computation: exact semantic factorization, a polynomially bounded reachable carrier image, polynomial-length canonical encodings with efficient equality, complete exact polynomial-time successor dynamics, polynomially bounded progression, and exact readout. The criterion is an audit schema for exact dynamic-programming arguments rather than a new complexity mechanism. The examples are stated as explicit restricted transition systems. For an Ising instance with an independently supplied background and fixed defect budget \(k\), we optimize over configurations differing from that background at at most \(k\) sites. An explicit frontier state machine is successor-closed, retains every admissible configuration, and has \(O(N^{k+1})\) carrier states. A periodic finite-defect input family is a contextual subclass of this constrained problem; periodicity does not itself imply the defect bound. For a fixed-cross-section tube, a finite frontier signature records occupancy, polymer connectivity, exterior connectivity, the active endpoint, and rear shielding. Its explicit transfer relation yields \(O(n^2)\) carrier states for the resulting longitudinally shielded polymer problem. The general shielded-polymer theorem remains conditional on exterior-state compression. A uniform-pairing example is presented only as an admitted transition-local normal form, while fixed-block symmetry gives an \(O(N^{2m})\) count for fixed \(m\).