Metraipolis › archive › dc_e82d8243dbf8
Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy — arXiv:2608.11782
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.11782
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T05:48:16.196Z
- SHA-256 of the archived text
c543a2166672d7f5942a0e548d2572fda9119171e6bca0b42456f098861cae7b- Stable URL of this page
https://metraipolis.com/documento/dc_e82d8243dbf8
How to cite
Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy — arXiv:2608.11782 — arXiv (en), https://arxiv.org/abs/2608.11782 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e82d8243dbf8 (Metraipolis archive dc_e82d8243dbf8, sha256 c543a2166672d7f5942a0e548d2572fda9119171e6bca0b42456f098861cae7b)
BibTeX
@misc{dce82d8243dbf8,
title = {Partial Path Interception in Derivation DAGs: Exact Reliability Laws and a Sharp Complexity Dichotomy — arXiv:2608.11782},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.11782},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e82d8243dbf8; sha256 c543a2166672d7f5942a0e548d2572fda9119171e6bca0b42456f098861cae7b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11782. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We introduce partial path interception on derivation DAGs (directed acyclic graphs), a combinatorial optimization problem arising from proof-valid caching: stored objects must be logical consequences of a premise base whose premises are erased independently, a query is recovered only while derivable from surviving premises and stored objects, and the queried object itself may not be stored, so reliability must come from premises or intermediate consequences. An exact residual-leaf law pins the recovery probability to a closed form in the exposed-leaf count and reduces design to weighted partial path interception (PPI) on the witness DAG. We classify PPI across its canonical regimes: it is NP-complete already on depth-two DAGs with leaf out-degree two and fixed-parameter intractable in the budget, ruling out efficient approximation schemes; it contains smallest T-edge subgraph as a special case, hence admits no approximation within the square root of the optimum under the Strongish Planted Clique Hypothesis, matched there by trivial leaf-only caching; whereas unique-path instances admit an exact dynamic program, bounded-treewidth instances are fixed-parameter tractable, and individual coverage admits a tight logarithmic greedy guarantee. Semantic-module caches are exactly optimal for shared workloads under exact module routing. An appendix prices transparency against a coded erasure benchmark. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.IT). Categorie arXiv: Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2608.11782 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T05:41:22.356Z dalla pagina https://arxiv.org/catchup/math.IT/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).