Magnetic Kernel Expansion as the Structural Origin ofWorst-Case SAT

IntroductionUnderstanding the structural origin of computational hardness remains central to complexity theory. Whiletraditional approaches emphasize branching and independent search paths, we propose that hardness emergesfrom the unavoidable expansion of a decisive constraint core.We formalize this core as the Magnetic Kernel (MK) and show that its growth directly governs computationalcomplexity.2 Magnetic Kernel FrameworkLet 𝐹 be a SAT instance.Definition 2.1. A Magnetic Kernel 𝑀𝐾(𝐹 ) ⊆ 𝐹 is a minimal set of clauses satisfying:𝐹 is satisfiable ⇐⇒ 𝑀𝐾(𝐹 ) is satisfiable.Define residual:𝑅(𝐹 ) = 𝐹 \ 𝑀𝐾(𝐹 ).3 Kernel Expansion TheoremTheorem 3.1. For a family of SAT instances 𝐹𝑛 with 𝑛 variables:If|𝑀𝐾(𝐹𝑛) | = Ω(𝑛),then any decision algorithm requires𝑇 (𝑛) ≥ 2Ω(𝑛) .Author’s Contact Information: Dr.Durgham Ahmad Ja’far Qaralleh - Jordan,Mutah