Metraipolis › archive › dc_b15bc628d382
Subexponential-Time Exact-One Hitting Set — arXiv:2611.00994
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.00994
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:45:36.710Z
- SHA-256 of the archived text
36669aaccbf6556b297833b119d7457e1717b4d555b7353dba4f7f5070781528- Stable URL of this page
https://metraipolis.com/documento/dc_b15bc628d382
How to cite
Subexponential-Time Exact-One Hitting Set — arXiv:2611.00994 — arXiv (en), https://arxiv.org/abs/2611.00994 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b15bc628d382 (Metraipolis archive dc_b15bc628d382, sha256 36669aaccbf6556b297833b119d7457e1717b4d555b7353dba4f7f5070781528)
BibTeX
@misc{dcb15bc628d382,
title = {Subexponential-Time Exact-One Hitting Set — arXiv:2611.00994},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.00994},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b15bc628d382; sha256 36669aaccbf6556b297833b119d7457e1717b4d555b7353dba4f7f5070781528},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00994. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Exact-One Hitting Set is one of Karp's original 21 NP-complete problems: given an explicitly listed family of subsets of an $r$-element ground set, decide whether a subset meets every input set in exactly one element. Combining our reduction with the fixed-width exact-counting theorem of OpenAI (2026), we obtain a deterministic polynomial-space algorithm that computes the exact number of feasible selections in time $2^{O(r\log\log(r+16)/\sqrt{\log(r+16)})}\operatorname{poly}(L+1)=2^{o(r)}\operatorname{poly}(L+1)$, where $L$ is the input length. The number and widths of the input sets are unrestricted. Known row selection retains at most $r+1$ input constraints, but their total width may remain quadratic. Our path representation of two-query counting cancellation constructs two ordinary 3-CNF formulas with at most $2r$ variables and $O(r^2)$ clauses each, whose model counts differ by the desired answer. The auxiliary-variable budget depends on the number of simultaneous conditions, not on their widths or on the numbers of witnesses. We extend this construction to signed equations with fixed bounded demands and positive integer coefficients. We also represent every explicitly listed Boolean relation of VC dimension at most one by binary clauses and signed exact-one equations on its original variables, obtaining the same two-query variable bound for unrestricted overlaps among such local constraints. A bounded-term version further handles fixed finite/cofinite local degree rules on arbitrary graphs. The path representation is related by variable elimination to existing marker--parity cancellation.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.00994 — 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-11-03T11:07:52.228Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).