An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912640130875392 |
|---|---|
| author | Lela, Marko |
| author_facet | Lela, Marko |
| contents | We introduce a model-agnostic MDL-style cost functional $K_C$ for resource-bounded classifiers and prove a Total-Variation stable reduction lemma ($A2^d$) for distribution-preserving many-to-one reductions. On a balanced distribution of random 3XOR instances (with co-rank $t'=Θ(n)$) we obtain a size-aware lower bound against P-uniform AC^0+log models: $\Pr[M=χ] \le \frac{1}{2} + s(N)\exp(-α_d m^{c/d})$ with an absolute $c \in (0,1)$ (e.g., $c=1/3$ gives $β_d=1/(3d)$). A deterministic, injective 3XOR->3SAT translation (four 3-clauses per XOR, no auxiliaries) is $δ=0$ measure-preserving on its image window; by $A2^d$ the bound transfers to 3SAT. This yields, to our knowledge, the first explicit $K_C$-reading of such size-aware bounds under a $δ=0$ measure-preserving reduction in small-depth circuit lower bounds. We provide artifacts (generator -> DIMACS -> verification) with match-rate 1.0. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR Lela, Marko Computational Complexity Information Theory Logic in Computer Science 68Q15, 68Q17 F.1.3; F.2.2 We introduce a model-agnostic MDL-style cost functional $K_C$ for resource-bounded classifiers and prove a Total-Variation stable reduction lemma ($A2^d$) for distribution-preserving many-to-one reductions. On a balanced distribution of random 3XOR instances (with co-rank $t'=Θ(n)$) we obtain a size-aware lower bound against P-uniform AC^0+log models: $\Pr[M=χ] \le \frac{1}{2} + s(N)\exp(-α_d m^{c/d})$ with an absolute $c \in (0,1)$ (e.g., $c=1/3$ gives $β_d=1/(3d)$). A deterministic, injective 3XOR->3SAT translation (four 3-clauses per XOR, no auxiliaries) is $δ=0$ measure-preserving on its image window; by $A2^d$ the bound transfers to 3SAT. This yields, to our knowledge, the first explicit $K_C$-reading of such size-aware bounds under a $δ=0$ measure-preserving reduction in small-depth circuit lower bounds. We provide artifacts (generator -> DIMACS -> verification) with match-rate 1.0. |
| title | An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR |
| topic | Computational Complexity Information Theory Logic in Computer Science 68Q15, 68Q17 F.1.3; F.2.2 |
| url | https://arxiv.org/abs/2509.14305 |