跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24918 · v1

Hardness of "Infinite Energy" Puzzles

《Infinite Energy》谜题的难度

首次提交 2026-11-19 02:49
版本更新 2026-11-19 02:49
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

Infinite Energy (by Light Potato, 2025) is a single-player puzzle in which one wires a network of sockets so that, after every power source is unplugged, energy keeps circulating and leaves every board energized. We study several variants of the game and the complexity of deciding whether an instance can be won. The variants can be played at https://infinite-energy-peer-review.netlify.app, which also has worked examples of the reduction techniques. The colorless game, with connectability given by an arbitrary matrix, is NP-hard (by reduction from Hamiltonian Path) and lies in PSPACE. We give a seven-socket instance winnable only by charging a temporary battery loop and then breaking it, so the natural "charge and keep" strategy fails. We reduce NP-membership to one conjecture: that every winnable instance has a winning play in which no socket is charged twice. Two variants bound the complexity more tightly. The unconstrained variant, in which connectability is unrestricted, is TC0\mathsf{TC}^0-complete under AC0\mathsf{AC}^0 Turing reductions (hence in L). The geometric variant, in which connectability is set by proximity of points in Rk\mathbb{R}^k, stays NP-hard for every fixed k≥2k \ge 2 via reduction from Hamiltonian Path over grid graphs. The one-dimensional case is open. The colored variant is NP-hard, though a matching upper bound remains open.

AI 论文解读

基于摘要 · 非全文审阅

论文研究单机解谜游戏 Infinite Energy 及其多个变体的判定复杂度,证明多数变体为 NP-hard,部分变体可精确刻画到 TC^0 完全或 PSPACE 上界。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:49 · 最新观测版本

Hardness of "Infinite Energy" Puzzles

Infinite Energy (by Light Potato, 2025) is a single-player puzzle in which one wires a network of sockets so that, after every power source is unplugged, energy keeps circulating and leaves every board energized. We study several variants of the game and the complexity of deciding whether an instance can be won. The variants can be played at https://infinite-energy-peer-review.netlify.app, which also has worked examples of the reduction techniques. The colorless game, with connectability given by an arbitrary matrix, is NP-hard (by reduction from Hamiltonian Path) and lies in PSPACE. We give a seven-socket instance winnable only by charging a temporary battery loop and then breaking it, so the natural "charge and keep" strategy fails. We reduce NP-membership to one conjecture: that every winnable instance has a winning play in which no socket is charged twice. Two variants bound the complexity more tightly. The unconstrained variant, in which connectability is unrestricted, is TC0\mathsf{TC}^0-complete under AC0\mathsf{AC}^0 Turing reductions (hence in L). The geometric variant, in which connectability is set by proximity of points in Rk\mathbb{R}^k, stays NP-hard for every fixed k≥2k \ge 2 via reduction from Hamiltonian Path over grid graphs. The one-dimensional case is open. The colored variant is NP-hard, though a matching upper bound remains open.

查看此版本解读 →查看此版本原文 ↗