Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2509.07000 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912631161356288 |
|---|---|
| author | von Liechtenstein, Maximilian Ralph Peter |
| author_facet | von Liechtenstein, Maximilian Ralph Peter |
| contents | We introduce a certified pruning framework that consolidates the principles of counterfactual consistency and their networked extensions into a single operational model, with consequences for both quantum foundations and cryptographic hardness. First, we formalize epsilon-counterfactual instrumentation and epsilon-stability, capturing noisy but testable constraints in laboratory contextuality experiments. Second, we extend these constraints to networks of contexts, yielding contextuality-type inequalities that apply globally across a CNF-SAT instance. Third, we implement a propagate-and-prune solver in which every learned clause is certified by a dual Farkas certificate verified in exact arithmetic. This guarantees soundness while enabling sub-exponential pruning: if the induced network provides a per-variable pruning rate rho in (0,1) under epsilon-stable propagation, the search runs in time (2-rho)^n. These bounds do not contradict ETH or SETH: the worst case remains exponential, but structured families admit provable speedups. In cryptography, the results highlight how such reductions could affect hardness margins in idealized primitives; in foundations, they motivate laboratory tests of counterfactual bounds as potential probes of computational complexity. We explicitly distinguish experimental epsilon, which quantifies laboratory visibility, from numerical epsilon, which is a solver tolerance. This builds directly on our earlier framework for epsilon-instrumentation, here integrated into certified pruning with dual certificates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07000 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Certified Pruning from Counterfactual Consistency: Exact Certificates and Structured SAT Families von Liechtenstein, Maximilian Ralph Peter Quantum Physics F.2.2; I.2.8; G.2.2 We introduce a certified pruning framework that consolidates the principles of counterfactual consistency and their networked extensions into a single operational model, with consequences for both quantum foundations and cryptographic hardness. First, we formalize epsilon-counterfactual instrumentation and epsilon-stability, capturing noisy but testable constraints in laboratory contextuality experiments. Second, we extend these constraints to networks of contexts, yielding contextuality-type inequalities that apply globally across a CNF-SAT instance. Third, we implement a propagate-and-prune solver in which every learned clause is certified by a dual Farkas certificate verified in exact arithmetic. This guarantees soundness while enabling sub-exponential pruning: if the induced network provides a per-variable pruning rate rho in (0,1) under epsilon-stable propagation, the search runs in time (2-rho)^n. These bounds do not contradict ETH or SETH: the worst case remains exponential, but structured families admit provable speedups. In cryptography, the results highlight how such reductions could affect hardness margins in idealized primitives; in foundations, they motivate laboratory tests of counterfactual bounds as potential probes of computational complexity. We explicitly distinguish experimental epsilon, which quantifies laboratory visibility, from numerical epsilon, which is a solver tolerance. This builds directly on our earlier framework for epsilon-instrumentation, here integrated into certified pruning with dual certificates. |
| title | Certified Pruning from Counterfactual Consistency: Exact Certificates and Structured SAT Families |
| topic | Quantum Physics F.2.2; I.2.8; G.2.2 |
| url | https://arxiv.org/abs/2509.07000 |