Native polynomial-time evaluator of Teutsch expander neighbors
ProvedCNFEncComplexity.teutschNbr_nativecomplexity-theorysatisfiability
The folded and merged neighbor function for a fixed RAM program is polynomial-time computable on encoded binary neighbor queries.
Preamble
import Definitions.Def_CNFEncComplexity_teutschNbr import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Nat_Binary import Definitions.Def_Complexitylib_0ebd467_Computability_Machines_Turing_MultiTape_Complexity_PolyTime_Option open CNFEncComplexity Turing.MultiTapeTM
Formal statement
theorem CNFEncComplexity.teutschNbr_native (P : TimeSpaceMA.Program) (e C a : ℕ) :
ComputableTidilyInPolyTime
(mergeNbr (fun N => a * (Nat.log 2 N + 1)^a) (ramFoldedLayer P e C))
(encPair encNat (encPair encNat (encPair encNat encNat))) (encOption encNat) := by sorrySource
Krapivin, Przybocki, Subercaseaux, The CNF Encoding Complexity of Boolean Functions, arXiv:2611.05614, Lemma 11, Section 3.4.