An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A{2}^d$), and an $A{C}^0$+log Lower Bound for 3SAT via Balanced 3XOR

Abstract

We introduce a model-agnostic MDL-style cost functional $K_C$ for resource-bounded classifiers and prove a Total-Variation stable reduction lemma ($A{2}^d$) for distribution-preserving many-to-one reductions. On a balanced distribution of random 3XOR instances (with co-rank $t^{\prime }=\Theta (n)$) we obtain a size-aware lower bound against P-uniform AC^0+log models: $\mathrm{Pr}[M=\chi ]\le \frac{1}{2}+s(N)\exp (-{\alpha }_d{m}^{c/d})$ with an absolute $c\in (0,1)$ (e.g., $c=1/3$ gives ${\beta }_d=1/(3d)$). A deterministic, injective 3XOR->3SAT translation (four 3-clauses per XOR, no auxiliaries) is $\delta =0$ measure-preserving on its image window; by $A{2}^d$ the bound transfers to 3SAT. This yields, to our knowledge, the first explicit $K_C$-reading of such size-aware bounds under a $\delta =0$ measure-preserving reduction in small-depth circuit lower bounds. We provide artifacts (generator -> DIMACS -> verification) with match-rate 1.0.

arXiv comment11 pages, 3 tables. Appendices A and B (switching parameters and correlation exponent; 2-core facts). Ancillary dataset on Zenodo (DOI 10.5281/zenodo.17138272). ORCID 0009-0008-0768-5184