Polynomial-time generation of the RAM tier sorter gates
ProvedCNFEncComplexity.Robson.memoryTierSorter_nativecomplexity-theorysatisfiability
If the supplied wire boundary is polynomial-time computable, the corresponding memory tier sorter gate list is polynomial-time computable.
Preamble
import Definitions.Def_CNFEncComplexity_RobsonMemoryTierGateList open CookLevin CNFEncComplexity.Robson CNFEncComplexity.RobsonCNF Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.Robson.memoryTierSorter_native
(stop : ℕ → ℕ → ℕ)
(hStop : ComputableTidilyInPolyTime (fun q : ℕ × ℕ => stop q.1 q.2) (encPair encUnary encUnary) encUnary) :
ComputableTidilyInPolyTime (fun q : ℕ × ℕ => memorySorter stop q.1 q.2)
(encPair encUnary encUnary) (encList gateEnc) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Theorem 10 (formalization support).