betaFeedback

WorksComputer Science

Hardness of "Infinite Energy" Puzzles

Abstract

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.

Introduction

Infinite Energy (by Light Potato, 2025) is a puzzle in which the player must assemble a circuit that stays powered after its power supply has been taken away. It was created for the 2025 GMTK Game Jam, an annual competition hosted by the game designer Mark Brown. Out of the 9,547 entries it ranked first as Brown’s personal favorite and tenth in the community vote for creativity. The original game can be played at https://lightpotato.itch.io/infinite-energy. We study it not only for this reception but also because its complexity sits in an unusual position among well-studied games, i.e., while a lower bound on hardness follows from reductions from known NP-hard problem, an upper bound on hardness remains elusive. To our knowledge, Infinite Energy does not fit cleanly into any family of puzzles whose complexity has been studied. We discuss this further, after providing an exposition of the game rules.

An instance is played on a collection of boards (the set BB), each holding one or more circular sockets (collectively PP) and displaying a cartoon face that smiles once the board is satisfied. Energy is supplied by external power sources (the set SS), drawn as octagonal units, and travels along directed wires that the player draws between sockets. In the full game a board also carries a color requirement, shown by the eyes of its face. Color is a separate constraint that we isolate in Appendix E and ignore until then, so the main text studies the colorless game. Two rules govern the flow of energy:

  1. The sockets on a board are intrinsically connected, so energizing any one of them energizes the whole board and makes the remaining sockets available as outgoing sources, and

  2. each socket admits at most one wire, so that a socket either transmits energy or receives it, but never both.

The object of the game is to keep the boards powered after every source has been disconnected, which compels the player to route energy into directed cycles that circulate without external input. Figure 1 follows a single play through this mechanism, and Figure 3 (§ 2) contrasts a small winnable instance with one that cannot be won.

Figure 1. A play of INFINITE ENERGY on an instance with one red power source (the octagon on the left) and four boards, each carrying a red color requirement shown by the red eyes of its face. (a) The initial configuration: every board is unenergized and the source is detached. (b) The source is attached and emits its color along a wire into the upper socket of the left vertical board. Two of its three sockets are joined into a directed cycle (the third stays free to pass energy on), and the board becomes energized red so its face smiles. The right vertical board is wired into a cycle of the same shape but remains unenergized, drawn cold, since no energy has yet entered it. (c) The source is detached. The charged cycle continues to circulate energy without it, and because sockets sharing a board are joined for free, the energy propagates along cross-board wires to the remaining boards. Every board now displays its requirement met, and the instance is won with no source attached. The sustaining directed cycle from (b) is drawn schematically in Figure 2.

Two unconstrained instances

Figure 3. Two unconstrained instances (final configurations. No source attached. Shaded sockets are energized). (a) A winnable instance: b∗b^* has three sockets, so two of them form a self-sustaining 2-cycle (charged earlier through ss, then ss removed) and the third exports energy to the other board. (b) An unwinnable instance: two boards of two sockets each. Here ∣P∣=2∣B∣|P| = 2|B|, but no board has three sockets, so any loop would occupy both sockets of each board it meets and leave none off the loop to charge it (Lemma 8). Once ss is removed nothing stays energized.

The step from Figure 1b to Figure 1c is where the mechanism operates. While the source is present it charges the connected structure and after it is removed the boards stay charged because the energy is trapped in a self-sustaining cycle. The player must therefore reach a state in which energy keeps propagating to every board after the source is gone. § 1.1 defines energization as the least fixed point of a monotone propagation rule, i.e., an instance is won when its energized set remains a nonempty fixed point after the sources are deleted. We encourage readers to try the variants at https://infinite-energy-peer-review.netlify.app.

This requirement places INFINITE ENERGY between two families of previously analyzed games: the trajectory games, such as platformers and sliding-block puzzles, whose solutions are sequences of moves [ADGV15,For10,HD05], and the consistency puzzles, such as Minesweeper, whose solutions are static labelings checked against local constraints [dB12,Kay00].

INFINITE ENERGY shares with the trajectory games a winning condition defined over a process rather than a state, so the final configuration does not certify a win. The wire graph left behind once the sources are withdrawn is a union of paths and cycles, and it does not record whether its loops were ever charged. In Figure 1b the un-energized cycle on the right is structurally identical to the charged one on the left, so the terminal graph underdetermines the energized set. A frozen frame of generalized Super Mario Bros. is uninformative in the same way, certifying nothing about the legality of the play that produced it [ADGV15]. The two families diverge in the certificate their processes admit. For a trajectory game the certificate is irreducibly a sequence of moves, checked by forward simulation, and generalized instances need not admit any short certificate, which places the reconfiguration framework underlying many of them in PSPACE [Hea04,HD09]. For INFINITE ENERGY one might hope that charging is monotone, so a static witness suffices: the final loops, each with a route in the connectability graph from a source to a free socket on one of its boards. This hope fails. Some instances are winnable only by charging a temporary battery, a loop built and then broken to free its sockets (Proposition 26), so the final loops do not on their own certify a win. They must also be chargeable in some order, with batteries where needed and without the charging routes competing for socket capacity, and the final wiring has erased that schedule. We therefore take the certificate to be a short winning play, and reduce the existence of one to a single conjecture: that a winning play never needs to charge any socket twice (§ 5). Without this conjecture, the problem is NP-hard and in PSPACE.

The game layers two further constraints on this mechanic. Wires have bounded length, so not every pair of sockets may be joined. In the standard game this restriction comes from a maximum wire length, and only sockets closer than that length can be connected. We relax it by taking connectability to be arbitrary, given by a connectability matrix MM supplied with the instance, and we return to the geometric version in § 6.

The second restriction assigns a color to each source and a color requirement to each board, with colors mixing additively as energy flows. We describe only the colorless game and defer the colored variant to Appendix § 13. Since the game is NP-hard without color, the colored variant is NP-hard too, but a matching upper bound remains open.

Our results. We separate the combinatorics of the game from its geometry. When connectability is unrestricted (MM all-ones), winnability reduces to two arithmetic conditions: at least 2∣B∣2|B| sockets and some board with at least three sockets (Theorem 7), and the induced predicate is TC0\mathrm{TC}^{0}-complete, hence in L (Theorems 10, 12, Proposition 11). With MM given arbitrarily the problem becomes NP-hard by reduction from Hamiltonian Path (Theorem 14), and lies in PSPACE (Theorem 17). We reduce NP-membership to a conjecture that recharge-free plays suffice (Conjecture 29, § 5), which would give NP-completeness. This hardness is not an artifact of unrealizable matrices. Every symmetric MM is realizable as a distance-threshold graph in Rn−1\mathbb{R}^{n-1}, where n=∣P∣+∣S∣n = |P| + |S| (Theorem 20), so the problem stays NP-hard under that geometric restriction (Corollary 21). In fixed dimension it remains NP-hard for every k≥2k \ge2 (Theorem 24). The one-dimensional case is open. Finally, the colored variant is NP-hard, though we do not settle a matching upper bound (Appendix § 13). Table 1 collects these results.

VariantComplexityReference
Unrestricted MM (all-ones)TC0\mathrm{TC}^{0}-completeTheorem 12
Arbitrary MMNP-hard, in PSPACETheorems 14, 17
Geometric, Rn−1\mathbb{R}^{n-1}NP-hard, in PSPACECorollary 21
Geometric, Rk\mathbb{R}^{k}, k≥2k \ge2NP-hard, in PSPACETheorem 24
Geometric, R1\mathbb{R}^{1}open—
ColoredNP-hardAppendix § 13

Table 1. Complexity of Infinite Energy across variants. For the NP-hard rows, NP-completeness would follow from Conjecture 29 (recharge-free plays suffice), which we state and support but do not prove.

Graph-Theoretic Formalization

Definition 1 (Instance). A (colorless) game instance is a tuple I=(P,S,B,M)I = (P, S, B, M) where

  • PP is a finite set of sockets.

  • SS is a finite set of sources, with P∩S=∅P \cap S = \varnothing.

  • BB is a partition of PP into nonempty boards, with B≠∅B \ne\varnothing (the empty instance wins vacuously and is excluded). We write b(p)b(p) for the board containing socket pp.

  • M∈{0,1}(P∪S)×(P∪S)M \in\{0, 1\}^{(P \cup S) \times(P \cup S)} is a symmetric connectability matrix, where M[x,y]=1M[x, y] = 1 means a wire may join xx and yy. We set M[s,s′]=0M[s, s'] = 0 for all s,s′∈Ss, s' \in S: a wire between two sources could never carry energy (a source only supplies, never receives, by Definition 2), so forbidding such wires loses no plays and lets us treat every socket uniformly.

A wire carries energy in one direction, so we model a wiring as a directed graph.

Definition 2 (Configuration). A configuration for I\mathcal{I} is a directed graph W=(P∪S,E)W = (P \cup S, E), where each edge is a wire oriented from the energy-supplying end to the receiving end, satisfying (with deg⁡+(v)\deg^{+}(v) and deg⁡−(v)\deg^{-}(v) being the out- and in-degree of vv in WW):

  1. One wire per part: deg⁡+(v)+deg⁡−(v)≤1\deg^{+}(v) + \deg^{-}(v) \le1 for every v∈P∪Sv \in P \cup S.

  2. Connectable: (x,y)∈E⇒M[x,y]=1(x,y) \in E \Rightarrow M[x,y] = 1.

  3. Sources only supply: deg⁡−(s)=0\deg^{-}(s) = 0 for every s∈Ss \in S (no wire points into a source).

Since the vertex set P∪SP \cup S is fixed by I\mathcal{I}, a configuration is determined by its wire set EE. We write the configuration as EE when only the wires matter.

Sockets on the same board pass energy without a wire. We record this with edges that do not count against the degree bound.

Definition 3 (Implicit edges and completion graph). The set of implicit edges is

EB={(p,q),(q,p)∣p≠q, b(p)=b(q)},E_B = \{(p,q),(q,p) \mid p \ne q,\ b(p) = b(q)\},

(energy flows either way within a board). The completion graph of a configuration W=(P∪S,E)W = (P \cup S,E) is G′=(P∪S,E∪EB)G' = (P \cup S,E \cup E_B).

Definition 4 (Loop). A loop is a directed cycle in G′G' whose edges alternate between wires (from EE) and implicit edges (from EBE_B):

p1→wirep2→impl.p3→wirep4→impl.⋯→impl.p1.p_1 \xrightarrow{\mathrm{wire}} p_2 \xrightarrow{\mathrm{impl.}} p_3 \xrightarrow{\mathrm{wire}} p_4 \xrightarrow{\mathrm{impl.}} \cdots\xrightarrow{\mathrm{impl.}} p_1.

Two facts follow immediately from Definition 4. First, because the edge types alternate around the cycle, every loop has even length 2k2k, using exactly kk wires and kk implicit edges. We call these kk wires the LL-edges of the loop LL. Each socket of LL carries exactly one of them. Second, every socket on a loop has one incoming and one outgoing cycle edge of which exactly one is a wire, so a loop never exceeds the one-wire-per-socket budget.

It remains to say how energy spreads and what it means to win.

Definition 5 (Energization). Fix a configuration WW. A socket is energized in WW if, in the completion graph G′G', it is reachable from some energized socket or a power source by a directed path of wires and implicit edges. A board is energized if at least one of its sockets is energized (equivalently, because of the implicit edges, if one socket is energized all the sockets on the board are). A loop is said to be charged in WW if every socket on it is energized in WW.

The current wiring does not by itself determine energization: a charged loop keeps its sockets energized even after the source that charged it is unplugged (Figure 2). Energization is therefore relative to a play’s history, not to the current wiring alone. Appendix A makes this precise with a recurrence ent\mathrm{en}_t over the configurations a play traverses. Informally, a socket is energized at step tt when it is reachable, through wires and board edges, from a source or from a loop that was charged earlier and whose wires still stand. This persistence is the source of the problem’s difficulty.

The two smallest loops, drawn as directed cycles

Figure 2. The two smallest loops (Definition 4), drawn as directed cycles. Solid arrows are wires of EE. Dashed arrows are implicit board edges of EBE_B, which cost no wire slot. Edge types alternate, so a loop of length 2k2k uses kk wires and kk implicit edges. The 2-cycle is the loop drawn as the red wires with both ends on the same board in Figure 1c.

Definition 6 (Move and play). A move is a pair m=(e,b)m=(e,b) where e=(p,q)e=(p,q) is a directed edge with p,q∈P∪Sp,q\in P\cup S and b∈{connect,disconnect}b\in\{\mathrm{connect},\mathrm{disconnect}\}. Applied to a configuration EE, the move yields

E⋅m={E∪{e},b=connect,E∖{e},b=disconnect,E\mathbin{\cdot}m = \begin{cases} E\cup\{e\}, & b=\mathrm{connect},\\ E\setminus\{e\}, & b=\mathrm{disconnect}, \end{cases}

and is legal at EE if E⋅mE\mathbin{\cdot}m is a valid configuration (Definition 2) and, additionally, e∉Ee\notin E when b=connectb=\mathrm{connect} and e∈Ee\in E when b=disconnectb=\mathrm{disconnect}.

A play is a finite sequence of moves m1,…,mTm_1,\ldots,m_T such that, writing E0=∅E_0=\varnothing and Et=Et−1⋅mtE_t=E_{t-1}\mathbin{\cdot}m_t, each mtm_t is legal at Et−1E_{t-1}. We call E0,…,ETE_0,\ldots,E_T the configurations traversed by the play.

Problem (Infinite Energy). Given an instance II, is there a play whose final configuration ETE_T connects no source yet leaves every board energized at TT (Appendix A)?

Unconstrained Infinite Energy is in P

The unconstrained variant Unconstrained-Infinite Energy is the special case in which the connectability matrix imposes no restriction: M[x,y]=1M[x,y]=1 for every socket–socket and source–socket pair (only source–source wires remain forbidden). The input is then only (P,S,B)(P,S,B) with S≠∅S\ne\varnothing, and we ask whether the instance is winnable, and we give a linear time algorithm.

Theorem 7. An unconstrained instance (P,S,B)(P,S,B) with S≠∅S\ne\varnothing is winnable if and only if

(i) ∣P∣≥2∣B∣\lvert P\rvert\ge2\lvert B\rvert, and

(ii) some board has at least 3 sockets.

Both conditions are checkable in O(∣B∣)O(\lvert B\rvert) time, so Unconstrained-Infinite Energy ∈P\in\mathrm{P}. Figure 3 shows a small winnable and a small unwinnable instance. The construction behind sufficiency is illustrated in Figure 5 (Appendix B).

Figure 5. The construction behind sufficiency in Theorem 7. The boards fall into three groups: the single bootstrap board b∗b^* (green, any board with at least three sockets), the boards with ∣b∣≥2|b| \ge2 (blue), and the singleton boards ∣b∣=1|b| = 1 (orange). Here F\mathcal{F} is the running pool of free energized sockets. (a) The initial instance, with ∣P∣≥2∣B∣|P| \ge2|B|. (b) Step 1 bootstraps a self-sustaining loop on b∗b^*. (c) Step 2 chains every board with ∣b∣≥2|b| \ge2, each net adding ∣b∣−2≥0|b| - 2 \ge0 sockets to F\mathcal{F}. (d) Step 3 spends one socket of F\mathcal{F} per singleton, which never runs out exactly when ∣P∣≥2∣B∣|P| \ge2|B|.

Sufficiency

Proof (sketch). Fix a board b∗b^* with ∣b∗∣≥3|b^*| \ge3 and bootstrap a self-sustaining 2-cycle on two of its sockets (charge through a source, then disconnect it). Maintain a pool F\mathcal{F} of free energized sockets. Energizing a board bb nets ∣b∣−2|b| - 2 to F\mathcal{F}, so processing boards in non-increasing size keeps F\mathcal{F} nonempty exactly when

∑b(∣b∣−2)=∣P∣−2∣B∣≥0.\sum_b (|b| - 2) = |P| - 2|B| \ge0.

Full proof in Appendix B.

Necessity

Both necessity proofs start from a winning final configuration WW, which by definition has no source connected yet every board energized. Since the base case of energization is empty without sources, all energy in WW originates from loops.

Lemma 8. If every board has at most 2 sockets, the instance is not winnable.

Proof (sketch). A charged loop’s sockets are all wire-saturated, so it can have been charged only through an implicit edge from an off-loop socket on a board it meets. Because implicit edges only exist within the same board, that board then has at least three sockets. Full proof in Appendix B.

Lemma 9. If ∣P∣<2∣B∣|P| < 2|B|, the instance is not winnable.

Proof (sketch). Contract each board to a node. Every energized board has in-degree at least one, so there are at least ∣B∣|B| socket–socket wires and each uses two of the ∣P∣|P| socket slots, so ∣P∣≥2∣B∣|P| \ge2|B|. Full proof in Appendix B.

Together, Lemmas 8 and 9 give the necessary direction of Theorem 7.

Hardness Lower Bound for Unconstrained Infinite Energy

Theorem 7 reduces Unconstrained-Infinite Energy to checking two arithmetic conditions on (P,B)(P,B): that ∣P∣≥2∣B∣|P| \ge2|B| and that some board has at least three sockets. We pin down the exact complexity of this predicate, which turns out to be far below P.

Membership in P already shows the unconstrained game is easy, but not how easy. The size test ∣P∣≥2∣B∣|P| \ge2|B| is a comparison of two counts, and we show below that this counting is not only sufficient but necessary. We use the standard circuit classes (see [AB09,Vol99]). AC0AC^0 is the class of languages decided by families of constant-depth, polynomial-size Boolean circuits over unbounded fan-in ∧,∨,¬\land,\lor,\lnot gates. TC0TC^0 is the same with unbounded fan-in threshold (equivalently majority) gates also allowed. Hence AC0⊆TC0⊆L⊆PAC^0 \subseteq TC^0 \subseteq L \subseteq P, and Majority ∉AC0\notin AC^0 [AB09,Vol99], so the inclusion AC0⊆TC0AC^0 \subseteq TC^0 is strict. Locating the predicate in TC0TC^0 but outside AC0AC^0 (under the encodings, uniformity, and reductions fixed below) is the sense in which its only difficulty is counting.

Theorem 10. Unconstrained-Infinite Energy ∈L\in L.

Proof. Scan the input once, maintaining three quantities: a running count of boards (∣B∣|B|), a running count of sockets (∣P∣=∑b∣b∣|P| = \sum_b |b|), and a single bit recording whether any board seen so far has more than two sockets. At the end, accept iff the bit is set and ∣P∣≥2∣B∣|P| \ge2|B|. Each counter holds a number at most the input size nn, so uses O(log⁡n)O(\log n) bits. The comparison ∣P∣≥2∣B∣|P| \ge2|B| is computable in the same space. Hence the procedure runs in deterministic logspace.

The predicate is also constant-depth: ∣P∣≥2∣B∣|P| \ge2|B| is one threshold over the input, and “some board exceeds two sockets” is a disjunction of local checks. This gives us the following proposition:

Proposition 11. Unconstrained-Infinite Energy ∈TC0\in TC^0.

We complement this with a matching lower bound: the problem is as hard as counting, so it cannot lie in AC0AC^0 [AB09,Vol99].

Theorem 12. Majority reduces to Unconstrained-Infinite Energy by a projection, in particular by a many-one AC0AC^0 reduction. Since Majority is TC0TC^0-complete under AC0AC^0 Turing reductions [Vol99], Unconstrained-Infinite Energy is TC0TC^0-complete under AC0AC^0 Turing reductions.

Proof (sketch). Map x∈{0,1}mx \in\{0,1\}^{m} to one board per bit: a three-socket board when xi=1x_i = 1 and a singleton when xi=0x_i = 0. Then ∣B∣=m|B| = m and ∣P∣=m+2s|P| = m + 2s with s=∑ixis = \sum_i x_i, so ∣P∣≥2∣B∣⟺s≥m/2|P| \ge2|B| \Longleftrightarrow s \ge m/2, and a 1-bit supplies the required three-socket board. Thus the instance accepts iff xx is majority-1. Each output board depends on one input bit, so the map is a projection, and a projection is an AC0AC^0 reduction. Full proof in Appendix B.

Two conventions make the completeness statement precise. We take the standard encoding in which the mm boards are listed in input order in fixed-width records, so the ii-th board is the one-bit projection above (later output positions do not depend on earlier bits), and we read TC0\mathrm{TC}^{0} and AC0\mathrm{AC}^{0} as dlogtime-uniform, under which Majority is complete and TC0⊆L\mathrm{TC}^{0} \subseteq\mathrm{L} hold. Majority accepts on ties (at least m/2m/2 ones), matching the size test. A projection gives only many-one Majority-hardness, which already places Unconstrained-Infinite Energy outside AC0\mathrm{AC}^{0}, whereas the preceding completeness uses that Majority is TC0\mathrm{TC}^{0}-complete under AC0\mathrm{AC}^{0} Turing reductions. Summarizing, Unconstrained-Infinite Energy sits at TC0⊆L⊆P\mathrm{TC}^{0} \subseteq\mathrm{L} \subseteq\mathrm{P}, a sharp drop from the NP-hardness of the full game.

Infinite Energy is NP-Hard

We reduce from Hamiltonian Path.

Definition 13 (Hamiltonian Path). Given an undirected graph G=(V,E)G=(V,E), decide whether GG has a Hamiltonian path: an ordering vσ(1),…,vσ(n)v_{\sigma(1)},\ldots,v_{\sigma(n)} of all n=∣V∣n=|V| vertices such that {vσ(k),vσ(k+1)}∈E\{v_{\sigma(k)},v_{\sigma(k+1)}\}\in E for every k<nk<n.

Hamiltonian Path is NP-complete [GJ79].

Theorem 14. Infinite Energy is NP-hard.

Construction. Given G=(V,E)G=(V,E) with V={v1,…,vn}V=\{v_1,\ldots,v_n\}, build an instance I=(P,S,B,M)\mathcal{I}=(P,S,B,M) as follows.

  • Node boards. For each viv_i a board bi={piL,piR}b_i=\{p_i^{L},p_i^{R}\} with two sockets.

  • Anchor board. One board b∗={p1∗,p2∗,p3∗}b^*=\{p_1^*,p_2^*,p_3^*\} with three sockets.

  • Source. A single source ss, so S={s}S=\{s\}.

Thus ∣P∣=2n+3|P|=2n+3 and B={b1,…,bn,b∗}B=\{b_1,\ldots,b_n,b^*\}. The connectability matrix MM permits exactly the following wires (and their symmetric entries):

(a) p1∗−p2∗p_1^*-p_2^* (the two anchor sockets, only to each other).

(b) s−p3∗s-p_3^* and p3∗−piXp_3^*-p_i^X for every ii and X∈{L,R}X\in\{L,R\}.

(c) piX−pjYp_i^X-p_j^Y whenever {vi,vj}∈E\{v_i,v_j\}\in E (i≠ji\ne j, X,Y∈{L,R}X,Y\in\{L,R\}).

All other entries of MM are 0. The construction is polynomial: O(n)O(n) sockets and an O(n2)O(n^2) matrix filled directly from the adjacency relation of GG. See Figure 4.

Correctness

Lemma 15 (Completeness). If GG has a Hamiltonian path, then I\mathcal{I} is winnable.

Proof (sketch). Wire s→p3∗s\to p_3^*, form the anchor loop p1∗→p2∗p_1^*\to p_2^*, disconnect ss, then follow the Hamiltonian path, wiring pσ(k)R→pσ(k+1)Lp_{\sigma(k)}^R\to p_{\sigma(k+1)}^L board by board. Full proof in Appendix § 8.

Reduction from Hamiltonian Path, showing an arbitrary graph and its corresponding game instance, and a Hamiltonian path mapped to a winning final configuration

Figure 4. (a) Given an arbitrary graph (on the left), we construct a game instance (on the right) where the connectability conditions correspond to the edges of the graph. (b) A HamPath on the graph corresponds to a winning final configuration and vice-versa. The anchor board is energized by connecting to the power source and then creating a loop of size 2 to sustain the energy.

Lemma 16 (Soundness). If I\mathcal{I} is winnable, then GG has a Hamiltonian path.

Proof (sketch). Only b∗b^* has three sockets, so the sole charged loop is {p1∗,p2∗}\{p_1^*,p_2^*\}. Energy leaves b∗b^* only through p3∗p_3^*, and the degree-two node boards force the energized region to be a single simple path visiting every one, i.e. a Hamiltonian path. Full proof in Appendix § 8.

Lemmas 15 and 16 prove Theorem 14.

Upper bounds: PSPACE, and NP modulo a conjecture

A win is defined by a play, a sequence of moves, not by a static picture: the same final wiring can be a win or a dead position, depending on whether its loops were ever charged. A game state is captured by the pair (current wiring, currently energized set), which takes polynomially many bits, and the next state is a function of the state and the move (Appendix § 7). Deciding whether a winning state is reachable from the empty wiring is therefore a reachability question over a state graph whose states have polynomial size.

Theorem 17. Infinite Energy ∈\in PSPACE.

For NP the certificate is a winning play, and two facts would suffice (Appendix § 7): a play is verifiable in time polynomial in its length (Proposition 25), and every winnable instance has a short winning play (Theorem 30). The obstacle to the second is that a win can require temporary batteries, loops charged only to be broken again. A seven-socket instance is winnable yet has no play that never breaks a charged loop (Proposition 26), so the natural “charge and keep” strategy fails outright. However, no socket ever needs its loop charged twice. Plays with this property, which we call recharge-free, have only O(∣P∣)O(|P|) charged loops (Lemma 28), and we conjecture that one of polynomial length always exists (Conjecture 29).

Theorem 18. Infinite Energy is NP-hard (Theorem 14) and lies in PSPACE (Theorem 17). If Conjecture 29 holds, then Infinite Energy is NP-complete.

Geometric Realizability of Connectability Matrices

The connectability matrix abstracts a physical layout. In the real game two sockets are joinable when they lie within a fixed wire length. We ask whether requiring MM to come from points in Rk\mathbb{R}^{k} weakens the hardness of Infinite Energy. In high dimension, geometry imposes no restriction, and hardness survives even in fixed, small dimension.

Definition 19 (k-realizable matrix). Let X=P∪SX = P \cup S. A symmetric matrix M∈{0,1}X×XM \in\{0,1\}^{X \times X} with zero diagonal is kk-realizable if there exist a map φ:X→Rk\varphi: X \to\mathbb{R}^{k} and a threshold d>0d > 0 such that, for all distinct u,v∈Xu,v \in X,

M[u,v]=1⟺∥φ(u)−φ(v)∥≤d.M[u,v] = 1 \Longleftrightarrow\lVert\varphi(u) - \varphi(v) \rVert\le d.

Equivalently, MM is the adjacency matrix of a distance-threshold graph in Rk\mathbb{R}^{k}.

Universal realizability in Rn−1\mathbb{R}^{n-1}

Theorem 20. Every symmetric M∈{0,1}n×nM \in\{0,1\}^{n \times n} with zero diagonal is (n−1)(n-1)-realizable.

The proof is in Appendix C. The reduction of Section 4 produces an arbitrary connectability matrix, and Theorem 20 places the sockets and sources of that matrix at points of Rn−1\mathbb{R}^{n-1} whose pairwise distances put a wire exactly between the pairs MM allows. The hardness of Infinite Energy therefore persists under this geometric restriction.

Corollary 21. Infinite Energy is NP-hard, and NP-complete if Conjecture 29 holds, even when MM is required to be realizable in Rn−1\mathbb{R}^{n-1}.

Hardness in fixed dimension

Corollary 21 leaves open whether hardness needs growing dimension. It does not. The reduction of Section 4 does not transfer directly: there the anchor socket p3∗p_3^* is connectable to every node socket, which is what lets a Hamiltonian path begin at any vertex. In a fixed-dimensional realization a single socket cannot sit within the threshold dd of arbitrarily many node boards spread across the lattice. We remove this requirement by fixing the start of the path, so that the anchor need only reach one node board.

Definition 22 (Anchored Hamiltonian Path). Given a graph G=(V,E)G = (V,E) and a vertex r∈Vr \in V, decide whether GG has a Hamiltonian path with rr as an endpoint.

Lemma 23. Anchored Hamiltonian Path is NP-complete even when GG comes with a grid embedding in which the endpoint rr has degree one and is the strictly highest vertex, so no other vertex lies in the row of rr or above it.

Proof (sketch). Reduce from Hamiltonian path between two specified boundary terminals s,ts,t of a grid graph [IPS82]. Attach to ss an arm of new degree-two grid vertices that leaves the bounding box through empty exterior cells and ends, above the whole figure, in a degree-one tip rr. Attach a similar arm to tt ending in r′r'. The arms force r,r′r,r' to be the path’s endpoints, and rr is placed as the highest vertex. Full proof in Appendix § 8.

Theorem 24. For every fixed k≥2k \ge2, no-color Infinite Energy is NP-hard (and NP-complete if Conjecture 29 holds) even when MM is realizable in Rk\mathbb{R}^k.

Proof (idea). Place each grid vertex’s two-socket board at its lattice point (sockets at (a±ε,b)(a \pm\varepsilon,b)), so boards are connectable iff the vertices are grid-adjacent, and put the anchor and source in the empty half-plane above the graph, reaching only the degree-one terminal rr. The reduction of § 4 then applies with the path forced to start at rr. Full construction in Appendix § 8, with a worked R2\mathbb{R}^2 example in Appendix § 12.

Membership: verification, PSPACE, and recharge-free plays

Fix an instance I=(P,S,B,M)\mathcal{I}=(P,S,B,M), with implicit edges EBE_B and completion graph G′(E)=(P∪S,E∪EB)G'(E)=(P\cup S,E\cup E_B) (Definition 3). A plug wire joins two sockets. A source wire has its tail in SS. A loop is an alternating directed cycle of G′(E)G'(E) (Definition 4), which uses at least one plug wire.

Energization is history-dependent

A charged loop keeps its sockets energized after its source is gone, so which sockets are energized depends on the play so far, not on the current wiring alone. Fix a play E0=∅,…,ETE_0=\varnothing,\ldots,E_T (Definition 6). Put en0=S\mathrm{en}_0=S and, for t≥1t\ge1, let sust\mathrm{sus}_t be the sockets lying on some directed cycle of G′(Et)G'(E_t) that uses a plug wire and all of whose sockets are in ent−1\mathrm{en}_{t-1}. Let ent\mathrm{en}_t be the least XX with S∪sust⊆X⊆P∪SS\cup\mathrm{sus}_t\subseteq X\subseteq P\cup S closed under flow (u∈Xu\in X and (u,v)∈Et∪EB(u,v)\in E_t\cup E_B imply v∈Xv\in X). A board is energized at tt if it meets ent\mathrm{en}_t. The play wins at TT if ETE_T carries no source wire and every board is energized at TT, i.e., the instance is winnable if some play wins.

This agrees with Definition 4. A directed cycle using a plug wire and lying in ent−1\mathrm{en}_{t-1} contains an alternating loop through that wire, so sust\mathrm{sus}_t is the flow-closure of the charged alternating loops’ sockets. The extra sockets it may name (coboard sockets carrying no wire) are energized anyway, so ent\mathrm{en}_t is unchanged. A loop, once all its sockets are in en\mathrm{en} while its wires stand, remains in sus\mathrm{sus} thereafter, which is the self-sustaining property of Figure 2.

Proposition 25. Whether a play of length TT wins is decidable in time polynomial in TT and ∣I∣|\mathcal{I}|.

Proof. Compute en0,…,enT\mathrm{en}_0,\ldots,\mathrm{en}_T in order. Given ent−1\mathrm{en}_{t-1}, restrict G′(Et)G'(E_t) to ent−1\mathrm{en}_{t-1} and take its strongly connected components. A socket lies in sust\mathrm{sus}_t iff its component contains a plug wire, since then it sits on a directed cycle through that wire inside ent−1\mathrm{en}_{t-1}. Then ent\mathrm{en}_t is the set reachable from S∪sustS\cup\mathrm{sus}_t in G′(Et)G'(E_t), by one graph search. Each step costs O((∣P∣+∣S∣)2)O((|P|+|S|)^2), and there are TT. Finally check that ETE_T has no source wire and every board meets enT\mathrm{en}_T.

A polynomial-space bound

Proof (of Theorem 17). A configuration is a wire set with each node on at most one wire, hence at most (∣P∣+∣S∣)/2(|P|+|S|)/2 plug wires and ∣S∣|S| source wires, described in O((∣P∣+∣S∣)log⁡(∣P∣+∣S∣))O((|P|+|S|)\log(|P|+|S|)) bits. A state is a pair (E,X)(E,X) with X=en⊆P∪SX=\mathrm{en}\subseteq P\cup S, again of polynomial size. By §A.1 the successor of (E,X)(E,X) under a legal move mm is (E⋅m,en′)(E\cdot m,\mathrm{en}'), where en′\mathrm{en}' is a function of XX and E⋅mE\cdot m computable in polynomial time. Winning states (no source wire, every board in XX) are recognizable in polynomial time. Deciding whether a winning state is reachable from (∅,S)(\varnothing,S) in this graph of 2poly2^{\mathrm{poly}} states is in NPSPACE=PSPACE\mathrm{NPSPACE}=\mathrm{PSPACE}.

A win can require temporary batteries

A win may charge a loop only to break it later, using the loop as a battery that keeps a board energized while other sockets are rewired. Batteries are not a convenience: some instances cannot be won without one. Call a play monotone if sus0⊆sus1⊆⋯\mathrm{sus}_0 \subseteq\mathrm{sus}_1 \subseteq\cdots, that is, if no charged loop is ever broken.

Proposition 26. Some winnable instance has no monotone winning play.

Proof. Let P={t}⊔{p,q,r}⊔{x,y,z}P = \{t\} \mathbin{\sqcup} \{p,q,r\} \mathbin{\sqcup} \{x,y,z\}, with these three sets as the boards, a single source ss, and

M={xp, xz, pq, pt, yr, qr, zs, rs}.M = \{xp,\ xz,\ pq,\ pt,\ yr,\ qr,\ zs,\ rs\}.

The source reaches board {p,q,r}\{p,q,r\} only at rr and board {x,y,z}\{x,y,z\} only at zz. Writing x‾\overline{\phantom{x}} for a disconnect, the play

s→r,x→z,p→q,s→r‾,r→y,r→y‾,p→q‾,p→t,y→rs\to r,\quad x\to z,\quad p\to q,\quad\overline{s\to r},\quad r\to y,\quad\overline{r\to y},\quad\overline{p\to q},\quad p\to t,\quad y\to r

wins: it lights {p,q,r}\{p,q,r\} from the source at rr, charges the battery loop pqpq, unplugs the source, relays energy through the freed socket rr by r→yr\to y to charge the loop xzxz, dismantles the battery to free pp, installs the delivery p→tp\to t, and relights {p,q,r}\{p,q,r\} from the now self-sustaining board {x,y,z}\{x,y,z\} by y→ry\to r. The final wiring {xz,yr,pt}\{xz,yr,pt\} carries no source wire and energizes all three boards.

No monotone play wins. To close xzxz, board {x,y,z}\{x,y,z\} must be energized with x,zx,z free, so energy must enter at the spare yy. The only wire at yy is yryr, so it arrives from rr, and rr must be energized yet free to carry yryr. Board {p,q,r}\{p,q,r\} must therefore be lit while rr is free. The source meets that board only at rr, so it cannot light it without holding rr, and {x,y,z}\{x,y,z\}, still uncharged at this point, cannot deliver into it. So the board is lit by one of its own loops, and only pqpq avoids rr. Thus every win charges the loop pqpq, which uses pp. The only wire into board {t}\{t\} is ptpt, so the win must also deliver through pp. A monotone play never breaks pqpq, so pp stays occupied and ptpt can never be installed. Hence the instance is winnable but not monotone-winnable, and the battery is unavoidable.

Recharge-free plays and membership

The winning play above breaks a loop but never rebuilds one: each socket enters sus\mathrm{sus} at most once. Call a play recharge-free if for every socket vv the set of steps with v∈sustv \in\mathrm{sus}_t is an interval, so that once a loop through vv is broken, no loop through vv is ever charged again. Recharge-freeness is strictly weaker than monotonicity: it allows the discharges that Proposition 26 forces, but forbids charging any socket twice.

The charging macro. Let RR be a charged wiring we will not disturb and LL a loop with a chosen closing wire e∈Le \in L. A support witness for LL over RR is a simple directed path QQ with R∪Q∪(L∖{e})R \cup Q \cup(L \setminus\{e\}) a valid wiring, both endpoints of ee free in it, and QQ running from a source or a socket energized by RR to a socket off LL but on a board of LL.

Lemma 27 (Charging macro). If RR is charged and (Q,L,e)(Q,L,e) is a support witness over RR, then LL can be charged in O(∣P∣)O(|P|) moves without disturbing RR.

Proof. Add the wires of QQ and of L∖{e}L \setminus\{e\}. The witness makes this valid. Energy from QQ’s origin reaches its endpoint, and the arc L∖{e}L \setminus\{e\} carries it around every board of LL, so all their sockets are energized while both endpoints of ee stay free. Add ee: the cycle is present with all its sockets energized at the previous step, so it becomes sustaining by the recurrence of §A.1. Remove QQ. The wires of LL remain, so LL stays charged. A simple path and a loop use O(∣P∣)O(|P|) wires.

Lemma 28. In a recharge-free play the loops that ever become charged are pairwise socket-disjoint. Hence at most ∣P∣/2|P|/2 loops are charged in all.

Proof. A socket carries at most one wire, so it lies on at most one loop at any step. If two loops charged at different steps shared a socket vv, then vv would leave sus when the first loop broke and re-enter it when the second charged, which recharge-freeness forbids. So the charged loops are pairwise socket-disjoint, and each uses at least two sockets.

Conjecture 29 (Recharge-free suffices). Every winnable instance has a recharge-free winning play of length polynomial in ∣P∣|P|.

Theorem 30. If Conjecture 29 holds, then Infinite Energy ∈NP\in\mathrm{NP}.

Proof. A play of polynomial length is verified in polynomial time (Proposition 25), so it is an NP certificate.

By Lemma 28 a recharge-free play charges only O(∣P∣)O(|P|) loops, each by an O(∣P∣)O(|P|) macro (Lemma 27). The content of Conjecture 29 is that the routes and discharges between these charges stay short, equivalently that a forced discharge never has to be undone. Across all instances with ∣P∣≤4|P| \le4 and several million further instances up to ∣P∣=8|P| = 8, every winnable instance had a recharge-free winning play, and no shortest winning play ever recharged a socket. Whether some family instead forces a recharge, and with it a superpolynomial minimal play, is open. Such a family would place Infinite Energy above NP and make the PSPACE bound of Theorem 17 close to tight.

Omitted proofs

Proof of Sufficiency in Theorem 7

Proof (of sufficiency). Fix a source ss and a board b∗b^* with ∣b∗∣≥3|b^*| \ge3, labelling its sockets p1,p2,p3,…p_1,p_2,p_3,\ldots

Bootstrap. Wire s→p1s \to p_1 (energizing b∗b^*), then wire p2→p3p_2 \to p_3. The pair {p2,p3}\{p_2,p_3\} now forms a loop (wire p2→p3p_2 \to p_3, implicit edge p3→p2p_3 \to p_2), and it is charged because p1p_1 is energized. Disconnect ss. The loop persists, so b∗b^* stays energized, and its remaining ∣b∗∣−2≥1|b^*| - 2 \ge1 sockets are free and energized.

Chaining. Maintain a pool F\mathcal{F} of free energized sockets, initialized to the ∣b∗∣−2|b^*| - 2 leftover sockets of b∗b^*. Process the remaining boards in order of non-increasing size. To energize a board bb, draw a wire f→qf \to q from some f∈Ff \in\mathcal{F} to a socket q∈bq \in b. This consumes ff and qq but energizes all of bb, returning its other ∣b∣−1|b| - 1 sockets to F\mathcal{F}. The net increase to ∣F∣|\mathcal{F}| is −1+∣b∣−1=∣b∣−2-1 + |b| - 1 = |b| - 2.

Processing larger boards first means every board with ∣b∣≥2|b| \ge2 (net change ≥0\ge0) is handled before any singleton (net change −1-1). When the first singleton is processed the pool has size ∑∣b∣≥2(∣b∣−2)\sum_{|b|\ge2}(|b| - 2), and the number of singletons is exactly −∑∣b∣=1(∣b∣−2)-\sum_{|b|=1}(|b| - 2). Their difference is ∑b∈B(∣b∣−2)=∣P∣−2∣B∣≥0\sum_{b\in B}(|b| - 2) = |P| - 2|B| \ge0 by (i). Hence F\mathcal{F} never empties prematurely, every board ends up energized, and no source is connected.

Proof of Lemma 8

Proof. WW contains at least one loop LL. Each socket of LL is incident to exactly one wire and one implicit edge, and the implicit edge joins it to its loop-neighbour on the same board. Hence every board meeting LL contributes at least two sockets to it. The sockets of LL are all wire-saturated, so for LL ever to have been charged, energy must have entered it through an implicit edge from a socket not on LL, lying on a board bb that also contains LL-sockets. That board has at least two LL-sockets plus this extra one, so ∣b∣≥3|b| \ge3, contradicting the assumption.

Proof of Lemma 9

Proof. In WW all remaining wires are socket–socket. Let ww be their number. Each wire uses two socket slots and each socket holds at most one, so w≤∣P∣/2w \le|P|/2.

Contract each board to a single node, turning each wire into a directed edge between board-nodes (an intra-board wire becomes a self-loop). Call the result G^\hat{G}, with exactly ww edges. Energy enters a board only through a wire into one of its sockets (implicit edges stay within a board), so every energized board has in-degree at least 1 in G^\hat{G}. As all ∣B∣|B| boards are energized, w=∑bdeg⁡G^−(b)≥∣B∣w = \sum_b \deg^-_{\hat{G}}(b) \ge|B|. Combining, ∣B∣≤w≤∣P∣/2|B| \le w \le|P|/2, i.e. ∣P∣≥2∣B∣|P| \ge2|B|.

Proof of Lemma 15 (Completeness)

Proof. Let vσ(1),…,vσ(n)v_{\sigma(1)}, \ldots, v_{\sigma(n)} be a Hamiltonian path. Wire s→p3∗s \to p_3^*, energizing b∗b^*, then wire p1∗→p2∗p_1^* \to p_2^* to form a charged loop, and disconnect ss. Now b∗b^* is self-sustaining and p3∗p_3^* is free and energized.

Wire p3∗→pσ(1)Lp_3^* \to p_{\sigma(1)}^L, energizing bσ(1)b_{\sigma(1)}. For k=1,…,n−1k = 1, \ldots, n-1, the edge {vσ(k),vσ(k+1)}∈E\{v_{\sigma(k)}, v_{\sigma(k+1)}\} \in E permits the wire pσ(k)R→pσ(k+1)Lp_{\sigma(k)}^R \to p_{\sigma(k+1)}^L, which energizes the next board. No source is connected and every board is energized, so II is winnable.

Proof of Lemma 16 (Soundness)

Proof. Consider a winning final configuration WW: no source is connected, yet every board is energized. With no sources, all energy originates from charged loops. Recall (proof of Lemma 8) that any charged loop must contain a board with at least three sockets. The only such board is b∗b^*, so every charged loop uses an anchor socket. Since p3∗p_3^* is not connectable to p1∗p_1^* or p2∗p_2^*, the only loop on b∗b^* is {p1∗,p2∗}\{p_1^*,p_2^*\}. Hence it is the sole source of energy, and the node boards carry no loop of their own.

Every node board is therefore energized by a directed path of wires and implicit edges starting at b∗b^*. The only wire leaving b∗b^* goes from p3∗p_3^* (its single free socket) to one node board. Each node board has exactly two sockets, each holding at most one wire, so once energy enters a board through one socket it can leave only through the other. The energized region is thus a single simple path

p3∗→bσ(1)→bσ(2)→⋯p_3^* \to b_{\sigma(1)} \to b_{\sigma(2)} \to\cdots

visiting distinct node boards. As all nn boards are energized, the path visits every one, so σ\sigma is a permutation of {1,…,n}\{1,\ldots,n\}. Each step bσ(k)→bσ(k+1)b_{\sigma(k)} \to b_{\sigma(k+1)} uses a wire, which exists only when {vσ(k),vσ(k+1)}∈E\{v_{\sigma(k)},v_{\sigma(k+1)}\} \in E. Hence vσ(1),…,vσ(n)v_{\sigma(1)},\ldots,v_{\sigma(n)} is a Hamiltonian path in GG.

Proof of Lemma 23

Proof. Membership is immediate (a path is a certificate). For hardness we reduce from the following form of grid-graph Hamiltonian path, which is NP-complete [IPS82]: given a grid graph GG and two vertices s,ts,t on the outer boundary of its embedding, decide whether GG has a Hamiltonian ss–tt path. Boundary terminals are what the standard construction produces. The only feature of the instance we use is that ss and tt each have an empty orthogonally adjacent exterior cell. Let GG sit inside a bounding box. From ss route a self-avoiding path of new grid vertices: step first into that empty neighbour, then move through exterior cells that stay at least two cells away from every vertex of GG, out of the bounding box and up, ending in a tip rr strictly above the box. Staying two cells clear makes the new vertices adjacent only to one another (and to ss at the first step), so the arm is a chain of degree-≤2\le2 vertices with a degree-one tip rr and creates no other adjacency with GG. Routing it above the box makes rr the strictly highest vertex. Attach a like arm to tt ending in a tip r′r', routed through the exterior on the opposite side and kept two cells clear of the first arm so the two do not interfere. The augmented graph G′G' is a grid graph. Because each arm is a chain of degree-≤2\le2 vertices, any Hamiltonian path of G′G' must traverse each arm end to end, and since r,r′r,r' have degree one they are forced to be the two endpoints. Deleting the arms turns a Hamiltonian path of G′G' into a Hamiltonian ss–tt path of GG, and conversely any such path extends through the arms. Hence G′G', with rr highest and of degree one, has a Hamiltonian path with endpoint rr iff GG has one from ss to tt.

Proof of Theorem 24

Proof (sketch). It suffices to treat k=2k=2, since any R2\mathbb{R}^{2} realization embeds in Rk\mathbb{R}^{k} by padding with zeros. We reduce from Anchored Hamiltonian Path on a grid graph (G,r)(G,r) with deg⁡(r)=1\deg(r)=1 (Lemma 23). Fix ε=0.01\varepsilon=0.01 and threshold d=1.05d=1.05.

Node boards. For each grid vertex v=(a,b)v=(a,b) create a board Bv={(a−ε,b),(a+ε,b)}B_v=\{(a-\varepsilon,b),(a+\varepsilon,b)\}. For adjacent vertices, horizontal or vertical, every socket pair is within dd: the farthest such pair is at distance 1+2ε=1.02≤d1+2\varepsilon=1.02\le d. For diagonal vertices the nearest pair is at distance (1−2ε)2+1≈1.40>d\sqrt{(1-2\varepsilon)^2+1}\approx1.40>d, and farther pairs are larger. Thus two node boards are connectable iff their vertices are grid-adjacent, and, as in Section 4, all four socket pairings between adjacent boards are available, so a Hamiltonian path can use distinct incoming and outgoing sockets at every internal board. (Intra-board pairings are immaterial: by Lemma 8 no two-socket board can sustain a charged loop.) Every node board has diameter 2ε2\varepsilon.

Anchor and source. By Lemma 23 embed GG with rr its strictly highest vertex and place rr at the origin, so every other vertex has y≤−1y \le-1 and the region y≥1y \ge1 is empty. Put p3∗=(0,1)p_3^*=(0,1), σ=(0.9,1)\sigma=(0.9,1), p1∗=(−2,1)p_1^*=(-2,1), p2∗=(−2,2)p_2^*=(-2,2), with anchor board b∗={p1∗,p2∗,p3∗}b^*=\{p_1^*,p_2^*,p_3^*\} and source σ\sigma. One checks: ∥p1∗−p2∗∥=1≤d\lVert p_1^*-p_2^*\rVert=1\le d (the anchor’s loop). ∥p3∗−(±ε,0)∥≈1.00005≤d\lVert p_3^*-(\pm\varepsilon,0)\rVert\approx1.00005\le d, so p3∗p_3^* connects to BrB_r, while ∥p3∗−p1∗∥=2\lVert p_3^*-p_1^*\rVert=2 and ∥p3∗−p2∗∥=5\lVert p_3^*-p_2^*\rVert=\sqrt{5} are both >d>d and ∥σ−(±ε,0)∥≈1.34>d\lVert\sigma-(\pm\varepsilon,0)\rVert\approx1.34>d, so p3∗p_3^* is not wireable to p1∗,p2∗p_1^*,p_2^* and σ\sigma reaches only p3∗p_3^*. Every other node board lies at y≤−1y\le-1, at distance >d>d from all four points.

This matrix is realized in R2\mathbb{R}^2 and matches the construction of § 4 with the single change that p3∗p_3^* is wireable only to BrB_r. Hence the only anchor loop is {p1∗,p2∗}\{p_1^*,p_2^*\}, energy leaves b∗b^* only through p3∗p_3^* into BrB_r, and the degree-two node boards force a single simple path covering them all. The completeness and soundness arguments of Theorem 14 then go through, now with the path forced to start at rr: I\mathcal{I} is winnable iff GG has a Hamiltonian path with endpoint rr. See Figure 6 for an example reduction.

Arbitrary grid graph and corresponding game instance for the $\mathbb{R}^2$ reduction

Figure 6. (a) Arbitrary grid graph on which a Hamiltonian Path must begin at the highlighted node. An edge exists between adjacent nodes on the grid. (b) Corresponding game instance, where the dotted lines denote connectability governed by a distance threshold. The R2\mathbb{R}^2 reduction of Theorem 24, drawn schematically. (a) A grid graph whose Hamiltonian path must end at the highlighted degree-one terminal rr. (b) The game instance: each vertex becomes a two-socket board at its lattice point, so two boards are connectable (dotted lines, distance ≤d\le d) iff the vertices are grid-adjacent. The anchor board and source sit in an empty region beside rr and reach only rr’s board. In the reduction proper (Theorem 24) rr is placed as the highest vertex with the anchor in the empty half-plane above it. Further examples are at https://infinite-energy-peer-review.netlify.app.

Proof of Theorem 12

Proof. Let x∈{0,1}mx\in\{0,1\}^m with s=∑i=1mxis=\sum_{i=1}^{m}x_i ones. Map xx to the instance with one board per bit:

bi={{pi,1,pi,2,pi,3},xi=1,{pi,1},xi=0,P=⋃i=1mbi,B={b1,…,bm}.b_i= \begin{cases} \{p_{i,1},p_{i,2},p_{i,3}\}, & x_i=1,\\ \{p_{i,1}\}, & x_i=0, \end{cases} \qquad P=\bigcup_{i=1}^{m}b_i,\qquad B=\{b_1,\ldots,b_m\}.

Here ∣B∣=m|B|=m and ∣P∣=3s+(m−s)=m+2s|P|=3s+(m-s)=m+2s, giving

∣P∣≥2∣B∣⟺m+2s≥2m⟺s≥m2.|P|\ge2|B|\Longleftrightarrow m+2s\ge2m\Longleftrightarrow s\ge\frac{m}{2}.

Moreover, when s≥m/2s\ge m/2 and m>0m>0 some bit is 1, so some board has three sockets and the second condition of Theorem 7 holds automatically. When s<m/2s<m/2 the size condition already fails. Thus the instance is accepted iff xx has a majority of ones. Each output board depends on a single input bit, so the map is a projection, and every projection is an AC0\mathrm{AC}^0 reduction. Since Majority is TC0\mathrm{TC}^0-complete under AC0\mathrm{AC}^0 Turing reductions [Vol99], and Unconstrained-Infinite Energy ∈TC0\in\mathrm{TC}^0 (Proposition 11), the problem is TC0\mathrm{TC}^0-complete under AC0\mathrm{AC}^0 Turing reductions.

Proof of Theorem 20

Proof. Write A=MA=M and pick λ>max⁡{1,−λmin⁡(A)}\lambda>\max\{1,-\lambda_{\min}(A)\}, so that B:=λI+AB:=\lambda I+A is positive semidefinite. Then BB is a Gram matrix: there are vectors z1,…,znz_1,\ldots,z_n with zi⊤zj=Bijz_i^\top z_j=B_{ij}. Hence ∥zi∥2=λ\lVert z_i\rVert^2=\lambda for all ii, and zi⊤zj=Aij∈{0,1}z_i^\top z_j=A_{ij}\in\{0,1\} for i≠ji\ne j, so

∥zi−zj∥2=2λ−2Aij={2λ−2,Aij=1,2λ,Aij=0.(1)\lVert z_i-z_j\rVert^2=2\lambda-2A_{ij}= \begin{cases} 2\lambda-2, & A_{ij}=1,\\ 2\lambda, & A_{ij}=0. \end{cases} \tag*{(1)}

Choosing threshold d2=2λ−1d^2 = 2\lambda- 1 separates the two cases: Aij=1⟺∥zi−zj∥≤dA_{ij} = 1 \Longleftrightarrow\lVert z_i-z_j\rVert\le d.

It remains to reduce the dimension. Translate by anchoring znz_n: set yi=zi−zny_i = z_i-z_n, so yn=0y_n = 0 and ∥yi−yj∥=∥zi−zj∥\lVert y_i-y_j\rVert= \lVert z_i-z_j\rVert for all i,ji,j. The threshold graph is unchanged. The yiy_i lie in span⁡{y1,…,yn−1}\operatorname{span}\{y_1,\ldots,y_{n-1}\}, a space of dimension at most n−1n-1. Identifying it with Rn−1\mathbb{R}^{n-1} via an orthonormal basis realizes MM in Rn−1\mathbb{R}^{n-1}. For further background, see standard sources such as [HK01,LLR95].

Remark 31. Theorem 20 is an existence statement about the matrix, so Corollary 21 classifies the variant whose input is a matrix promised to be realizable. The coordinates it produces are real and need not have polynomial bit-length. The fixed-dimension reduction of Theorem 24 is different: it outputs explicit rational coordinates (lattice points offset by ε=0.01\varepsilon= 0.01, threshold d=1.05d = 1.05) of polynomial precision, so it is a reduction to the explicit-coordinate problem.

Example of the R2\mathbb{R}^2 reduction

Extension: the color-constrained variant, and open directions

This appendix records the colored extension and the questions it raises. The only complexity result here is an easy inherited hardness, and the more interesting questions are open. We give the model, note NP-hardness, and explain why the colorless membership argument does not carry over.

We extend the colorless game of § 1 with colors. The mechanic is the additive mixing of light: combining colored beams only ever adds primaries, never removes them, so mixing is modeled by union and named colors are abbreviations for subsets of primaries.

Color algebra. Fix a finite set of primary colors C′C'. The figures use the three additive primaries red, green, and blue. A color is a nonempty subset of C′C', and Col⁡=P(C′)∖{∅}\operatorname{Col} = \mathcal{P}(C') \setminus\{\emptyset\}. Colors mix by union, A⊕B=A∪BA \oplus B = A \cup B, an operation that is commutative, associative, and idempotent. The familiar names label elements of Col⁡\operatorname{Col}:

{red,blue}=purple,{red,green}=yellow,\{\text{red},\text{blue}\} = \text{purple}, \qquad\{\text{red},\text{green}\} = \text{yellow},
{blue,green}=cyan,C′=white.\{\text{blue},\text{green}\} = \text{cyan}, \qquad C' = \text{white}.

We adjoin a distinguished symbol ⋆∉Col⁡\star\notin\operatorname{Col} denoting the any-color requirement.

Instance. Extending Definition 1, a colored instance I=(P,S,B,M,χ,F)\mathcal{I} = (P,S,B,M,\chi,F) adds to a colorless instance (P,S,B,M)(P,S,B,M) two maps:

  • χ:S→Col⁡\chi: S \to\operatorname{Col} assigns a color to each power source.

  • F:B→Col⁡∪{⋆}F:B\to\operatorname{Col}\cup\{\star\} assigns a color requirement to each board.

Configurations, wires, implicit edges, loops, and the energized sets ent⁡\operatorname{ent} are exactly as in Section 1 and Appendix A. Colors are on top of energization and do not affect which sockets are energized.

Color propagation. Fix a play E0,…,ETE_0,\ldots,E_T (energization is as in Appendix A). Color accumulates along the play by the same flow, and transmission is gated by energization: a socket passes its color along an edge only while it is energized. For a socket p∈Pp\in P, its color col⁡t(p)\operatorname{col}_t(p) is the least solution of

col⁡t(p)=⨁{χ(s)∣s∈S, s reaches p in G′(Et′), t′≤t}⊕⨁(u,p)∈Et′∪EB, t′≤tu∈ent⁡t′col⁡t′(u)\operatorname{col}_t(p)=\bigoplus\left\{\chi(s)\mid s\in S,\ s\text{ reaches }p\text{ in }G'(E_{t'}),\ t'\le t\right\}\oplus\bigoplus_{\substack{(u,p)\in E_{t'}\cup E_B,\ t'\le t\\u\in\operatorname{ent}_{t'}}}\operatorname{col}_{t'}(u)

i.e. the union of the colors of every source whose energy has reached pp at any point, propagated forward through wires, implicit edges, and around charged loops. We take this permanent-memory model: a socket keeps every primary it has ever received, so col⁡t(p)\operatorname{col}_t(p) never shrinks, but by the gate it passes color on only while energized. For definiteness col⁡t(s)=χ(s)\operatorname{col}_t(s)=\chi(s) for a source ss, and col⁡t(p)=∅\operatorname{col}_t(p)=\varnothing for a socket never energized by step tt. Retaining a color while dark thus differs from transmitting one: on two singleton boards {a},{b}\{a\},\{b\}, wiring a red source to aa, unplugging it, then adding a→ba\to b leaves bb colorless, because aa is dark when a→ba\to b is present. A reset-on-de-energization variant is a different model with a different recurrence. The effective color of an energized board bb at time tt is

col⁡t′(b)=⨁{col⁡t(p)∣p∈b, p energized in Et}.\operatorname{col}'_t(b)=\bigoplus\left\{\operatorname{col}_t(p)\mid p\in b,\ p\text{ energized in }E_t\right\}.

See Figure 7 and Figure 8 for examples.

Figure 7. A colored play. (a) The initial configuration. The rectangle on the top right of each board shows its color requirement FF, and the source cannot reach the lower one-socket board because MM forbids the wire (too far away). (b) In step 1 the source is wired into the board whose requirement is blue. In step 2 a loop is formed on that board. (c) In step 3 (dotted) the source is disconnected and in step 4 the now self-sustaining board energizes the lower board through a cross-board wire. Every board meets its requirement, so the instance is won.

Color mixing and propagation on a loop

Figure 8. Color mixing and propagation on a loop. (a) A socket on a board sustained by a purple loop exports purple. (b) A blue loop spanning four sockets on two boards. (c) Disconnecting the blue source and then connecting a red source turns the loop purple (blue ⊕\oplus red), and the new color propagates to all four sockets and both boards’ colors gets updated. Panel (c) shows why the order of source connections and disconnections matters in the colored game.

Board satisfaction and the decision problem. A board bb is satisfied at tt if it is energized in EtE_t and its requirement is met exactly:

F(b)=⋆orcol⁡t′(b)=F(b).F(b) = \star\qquad\text{or} \qquad\operatorname{col}'_t(b) = F(b).

Colored Infinite Energy Given a colored instance I=(P,S,B,M,χ,F)\mathcal{I} = (P, S, B, M, \chi, F), does there exist a play whose final configuration ETE_T connects no source yet leaves every board satisfied?

Hardness.

Proposition 32. Colored Infinite Energy is NP-hard.

Proof. Colorless Infinite Energy is the special case in which color is vacuous. Given a colorless instance (P,S,B,M)(P, S, B, M), take a single primary C′={∙}C' = \{\bullet\}, set χ(s)={∙}\chi(s) = \{\bullet\} for every s∈Ss \in S, and F(b)=⋆F(b) = \star for every b∈Bb \in B. Then every energized board is satisfied, so the colored instance is winnable iff the colorless one is. The map is identity on (P,S,B,M)(P, S, B, M) and constant on χ,F\chi, F, hence a polynomial-time (indeed projection) reduction. NP-hardness follows from Theorem 14.

Open problems. The upper bound is open, and for a sharper reason than in the colorless case. There, whether a board is energized does not depend on the order in which sources are used, which is what the short-play route (Theorem 30, itself conditional) exploits. With colors the requirement col⁡′(b)=F(b)\operatorname{col}'(b) = F(b) is an exact match while color only accumulates (Figure 8), so a board can be over-colored and never corrected. Meeting every requirement at once then constrains the order in which sources are connected and disconnected across the whole play, which the final configuration does not record. We leave three questions. (i) Is colored Infinite Energy in NP? (ii) Is it hard for a class above NP? It is in PSPACE by the state-space bound of Theorem 17, which applies verbatim once colors are added to the state. (iii) Does the reset-on-de-energization model differ in complexity from the permanent-memory one above?

References

  1. [1]S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  2. [2]G. Aloupis, E. D. Demaine, A. Guo, and G. Viglietta. Classic Nintendo games are (computationally) hard. Theoretical Computer Science, 586:135–160, 2015.arxiv.org/abs/1203.1895
  3. [3]M. de Bondt. The computational complexity of Minesweeper, 2012. arXiv preprint arXiv:1204.4659.arxiv.org/abs/1204.4659
  4. [4]M. Forísek. Computational complexity of two-dimensional platform games. In P. Boldi and L. Gargano, editors, Fun with Algorithms (FUN 2010), volume 6099 of LNCS, pages 214–227. Springer, 2010.DOI
  5. [5]M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  6. [6]R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1–2):72–96, 2005.DOI
  7. [7]R. A. Hearn and E. D. Demaine. Games, Puzzles, and Computation. A K Peters, 2009.DOI
  8. [8]R. A. Hearn. The complexity of sliding-block puzzles and plank puzzles. In B. Cipra, E. D. Demaine, M. L. Demaine, and T. Rodgers, editors, Tribute to a Mathematician. A K Peters, 2004.
  9. [9]P. Hliněný and J. Kratochvíl. Representing graphs by disks and balls (a survey of recognition-complexity results). Discrete Mathematics, 229(1–3):101–124, 2001.DOI
  10. [10]A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter. Hamilton paths in grid graphs. SIAM Journal on Computing, 11(4):676–686, 1982.DOI
  11. [11]R. Kaye. Minesweeper is NP-complete. The Mathematical Intelligencer, 22(2):9–15, 2000.DOI
  12. [12]N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.
  13. [13]H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999.

Paper details

vlnc:W_qa3xtjjq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents