Encoding-Invariant Variance Amplification and the Failure of Encoding-Invariant Collapse: A Diagnostic Probe
Fuente:
Zenodo
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Recurso digital |
| Veröffentlicht: |
Zenodo
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866901744243441664 |
|---|---|
| author | De Jesus, Elias |
| author_facet | De Jesus, Elias |
| contents | <p>We report a pair of controlled computational probes investigating whether variance propagation in constraint satisfaction problems is invariant under polynomial-time re-encoding. Variance behavior is quantified using a persistence gradient, defined as the logarithmic derivative of relational variance with respect to instance size.</p> <p>In the first probe, we study XOR-SAT under three distinct encodings: canonical XOR clauses, expanded CNF gadget encodings, and linear-algebraic representations over GF(2). Across all encodings, relational variance exhibits consistent amplification with a strictly positive persistence gradient, indicating encoding-invariant variance amplification at fixed constraint density.</p> <p>In the second probe, we test for encoding-invariant variance collapse in graph reachability using local-transition, matrix-powering, and CSP-style encodings. In contrast to XOR-SAT, the sign of the persistence gradient varies across encodings, with amplification observed under local-transition encodings and weak collapse or stability under global encodings. This falsifies the hypothesis that variance collapse is encoding-invariant.</p> <p>Taken together, these results demonstrate a structural asymmetry: variance amplification can be an intrinsic property of a constraint operator, while variance collapse is observer-dependent and algorithm-specific. The findings clarify why variance collapse cannot define tractability, and why encoding-invariant amplification is a more robust diagnostic for structural hardness. No claims are made regarding complexity class separations.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_18236483 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Encoding-Invariant Variance Amplification and the Failure of Encoding-Invariant Collapse: A Diagnostic Probe De Jesus, Elias • computational complexity • constraint satisfaction problems • encoding invariance • variance propagation • persistence gradient • XOR-SAT • graph reachability • algorithmic observables • structural hardness • observer dependence • complexity diagnostics <p>We report a pair of controlled computational probes investigating whether variance propagation in constraint satisfaction problems is invariant under polynomial-time re-encoding. Variance behavior is quantified using a persistence gradient, defined as the logarithmic derivative of relational variance with respect to instance size.</p> <p>In the first probe, we study XOR-SAT under three distinct encodings: canonical XOR clauses, expanded CNF gadget encodings, and linear-algebraic representations over GF(2). Across all encodings, relational variance exhibits consistent amplification with a strictly positive persistence gradient, indicating encoding-invariant variance amplification at fixed constraint density.</p> <p>In the second probe, we test for encoding-invariant variance collapse in graph reachability using local-transition, matrix-powering, and CSP-style encodings. In contrast to XOR-SAT, the sign of the persistence gradient varies across encodings, with amplification observed under local-transition encodings and weak collapse or stability under global encodings. This falsifies the hypothesis that variance collapse is encoding-invariant.</p> <p>Taken together, these results demonstrate a structural asymmetry: variance amplification can be an intrinsic property of a constraint operator, while variance collapse is observer-dependent and algorithm-specific. The findings clarify why variance collapse cannot define tractability, and why encoding-invariant amplification is a more robust diagnostic for structural hardness. No claims are made regarding complexity class separations.</p> |
| title | Encoding-Invariant Variance Amplification and the Failure of Encoding-Invariant Collapse: A Diagnostic Probe |
| topic | • computational complexity • constraint satisfaction problems • encoding invariance • variance propagation • persistence gradient • XOR-SAT • graph reachability • algorithmic observables • structural hardness • observer dependence • complexity diagnostics |
| url | https://doi.org/10.5281/zenodo.18236483 |