Polynomial-time addressing of the RAM memory tier sorter inputs
ProvedCNFEncComplexity.Robson.memoryTierSorterSource_nativecomplexity-theorysatisfiability
If the supplied wire boundary is polynomial-time computable, the input wire to the sorted-window circuit is polynomial-time computable from the layout sizes, tier, record lane, and bit index.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierGateList open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.Robson.memoryTierSorterSource_native
(stop : ℕ → ℕ → ℕ)
(hStop : ComputableTidilyInPolyTime (fun q : ℕ × ℕ => stop q.1 q.2)
(encPair encUnary encUnary) encUnary) :
ComputableTidilyInPolyTime
(fun q : (((ℕ × ℕ) × ℕ) × ℕ) × ℕ =>
memorySorterSource stop q.1.1.1.1 q.1.1.1.2 q.1.1.2 q.1.2 q.2)
(encPair (encPair (encPair (encPair encUnary encUnary) encUnary) encUnary) encUnary)
encUnary := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).