Metraipolis › archive › dc_a0a0b59e487c
Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs — arXiv:2608.23506
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.23506
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T09:17:46.405Z
- SHA-256 of the archived text
42fd820192fdc18d54100e3e747d98df59da12ee8042eaf59d008386bef57ac5- Stable URL of this page
https://metraipolis.com/documento/dc_a0a0b59e487c
How to cite
Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs — arXiv:2608.23506 — arXiv (en), https://arxiv.org/abs/2608.23506 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a0a0b59e487c (Metraipolis archive dc_a0a0b59e487c, sha256 42fd820192fdc18d54100e3e747d98df59da12ee8042eaf59d008386bef57ac5)
BibTeX
@misc{dca0a0b59e487c,
title = {Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs — arXiv:2608.23506},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.23506},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a0a0b59e487c; sha256 42fd820192fdc18d54100e3e747d98df59da12ee8042eaf59d008386bef57ac5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.23506. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in cs.CC). Categorie arXiv: Computational Geometry (cs.CG) ; Computational Complexity (cs.CC); Computational Physics (physics.comp-ph). Pagina del lavoro: https://arxiv.org/abs/2608.23506 — 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-18T09:17:26.766Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).