LaserTank is NP-complete

Per Alexandersson; Petter Restadh

REVIEW 3 major objections 4 minor 8 references

LaserTank is NP-complete

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the puzzle game LaserTank is NP-complete, even when the tank is restricted to sideways movement in a single column and the board contains only mirrors and solid blocks.

desk verdict The NP-hardness reduction looks solid and the result is new, but Lemma 1's in-NP proof has a false reversibility inference that needs a visited-state fix. read the letter →

arxiv 1908.05966 v1 pith:E2KP764U submitted 2019-08-16 cs.CC math.CO

Per Alexandersson , Petter Restadh This is my paper · ORCID

classification cs.CCmath.CO MSC 68Q17

keywords NP-completenessLaserTank3-SATcomputationalcomplexitypuzzlegamepolynomialreductiongadgetconstructionmirrorsandsolidblocks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Solving arbitrary LaserTank puzzles is NP-complete, the paper claims: a polynomial-time solver would settle every 3-SAT instance and therefore would imply P = NP. The result holds under unusually strong restrictions, with the tank only moving sideways within one column and the only board pieces being mirrors and solid blocks. The proof reduces 3-SAT to LaserTank by encoding each variable, each clause, and the conjunction of clauses as small mirror-and-block gadgets wired together on a polynomially larger board. Solving the resulting puzzle is equivalent to finding a satisfying assignment, so hardness transfers to the game.

What carries the argument

The argument is carried by a set of four small board gadgets—AND, THREE-OR, LITERAL, and SWITCH—each a pattern of mirrors, movable blocks, and solid walls. A gadget reacts to an incoming laser shot on a designated input corridor and produces an outgoing shot on an output corridor, so it behaves like a boolean gate whose wires are laser paths. The overall board wires these gates into a 3-SAT circuit: the single AND-gadget, gated behind every clause, can fire only if each clause supplies a satisfied literal, and hitting the goal requires that fire. The polynomial board-size bound is what makes the construction a polynomial-time reduction.

What would settle it

Arrange four mirrors as a closed rectangle, fire the laser into the ring, and check whether the beam keeps reflecting forever without hitting a solid block, movable block, or a mirror's pushable short edge. If such a cycle exists under the described rules, the claim that every shot stops in fewer than $4n$ steps is false, and the proof's membership-in-NP argument needs replacement.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: LaserTank is NP-complete. The proof constructs a polynomial-time reduction from 3-SAT. One literal-gadget per variable produces either the literal or its negation, one three-or-gadget per clause collects the three literals, and a multi-input and-gadget combines all clauses so that its output is the only route to the goal. Switch-gadgets let a single literal's laser shot reach several clauses, and the construction is sized at $(7v+9c+4)(7c+9)$ for $v$ variables and $c$ clauses. The paper also notes that movable blocks can be replaced by mirrors and that the tank can be allowed to move in all four directions, so the hardness statement covers those variants as well.

Load-bearing premise

The paper's proof that a solution can be checked quickly assumes that because the laser's path is reversible it can never get stuck in an endless loop; that is false, because a reversible deterministic path can still go around a closed cycle of mirrors forever.

Editorial extensions

If this is right

Unless P = NP, no polynomial-time algorithm can solve arbitrary LaserTank puzzles, since any such algorithm would also solve 3-SAT.
Hardness survives the restricted rules: sideways tank movement in a single column, only mirrors and solid blocks on the board, and even a variant with no movable blocks.
Every 3-SAT formula with $v$ variables and $c$ clauses can be turned into a LaserTank board of size $(7v+9c+4)(7c+9)$, so the reduction is constructive and explicit.
A solution of the puzzle translates back to a satisfying assignment in polynomial time; any variable the solution leaves undecided can simply be set to true.
The same restricted piece set implies that the graphing-calculator game Laser Mayhem is also NP-complete.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The NP-membership argument in Lemma 1 is the fragile part: it equates time-reversibility with termination, but reversible deterministic systems can cycle, so the proof needs a different bound, such as detecting a repeated global state, and the paper does not supply one.
The gadget construction is modular enough to be reused: any ray-based puzzle with pushable mirrors and movable blocks is a candidate for the same 3-SAT encoding, so the result may transfer to other games of that family.
Because hardness already appears when the tank cannot navigate freely, the complexity is driven by the laser-mirror dynamics rather than movement planning; a natural follow-up is to test whether a stationary tank with only a few fixed firing positions remains NP-complete.
The explicit size formula suggests a practical use: small 3-SAT formulas could be compiled into compact LaserTank levels, and one could search for minimal hard instances, though the paper does not attempt that.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline: this is a new NP-completeness result for a previously unstudied puzzle, and the NP-hardness reduction looks believable; the problem is Lemma 1, which doesn't prove what it claims. The reversibility argument is simply false—finite reversible systems can have cycles. The fix is standard: track visited directed states during the laser simulation; a repeat means the shot never terminates, and any terminating shot is a simple path of at most 4n states. With that change, membership in NP goes through.

What I like: the authors chose a minimal subset of LaserTank pieces, restrict the tank to a single column, and still get a clean reduction from 3-SAT. The board-size formula is explicit and polynomial. The gadgets are standard but well-chosen; the figures are helpful. The paper is honest about the scope, noting the Viglietta framework and showing the result extends to movable blocks and four-direction tank movement.

Soft spots, in proportion: Lemma 1 is the main one, and it's real but localized. The text 'time-reversible implies impossible... infinite loop' is plainly wrong; a deterministic reversible map on a finite set can have cycles. I'd also want the gadget correctness arguments expanded from 'notice that' to a short case analysis; as written, they're plausible but not fully rigorous. That's a standard request for this kind of paper, not fatal. There's also a minor issue: the simulation bound in Lemma 1 assumes the board is static during a shot; in the game, a shot ends when it pushes a mirror or block, so that part is fine, but the paper doesn't explicitly justify it.

Bottom line: the result is likely correct after a small repair to Lemma 1. If you work on puzzle complexity, it's worth citing. The paper deserves a serious referee; I'd send it out with a request to fix the lemma and tighten the gadget proofs.

Referee Report

3 major / 4 minor

Summary. The paper claims to prove that the puzzle game LaserTank is NP-complete, even under strong restrictions: the tank moves only sideways and the board uses only mirrors and solid blocks. The proof is a direct reduction from 3-SAT, constructing gadgets for logical AND, OR, and literals, and then assembling them into a puzzle whose size is polynomial in the formula size. The paper also claims that a solution to the resulting puzzle can be translated back to a satisfying assignment, and that the game is in NP via Lemma 1, which asserts that each laser shot terminates in O(n) steps.

Significance. If the result is correct, it is a valuable addition to the complexity-theoretic study of puzzle games: it settles the complexity of LaserTank, gives a strong restricted version (single-column tank movement, few piece types), and does not rely on generic meta-theorems but gives an explicit, self-contained construction. The reduction is from an established NP-complete problem and the board-size formula is explicitly polynomial. The paper also observes that the construction can be adapted to a version with no movable blocks and to unrestricted tank movement. These strengths make the underlying approach promising, but the current manuscript has a serious gap in the in-NP proof and lacks rigorous gadget analysis.

major comments (3)

[Lemma 1 (Section 2)] The proof of Lemma 1 asserts that time-reversibility of laser movement implies that a laser shot cannot enter an infinite loop. This implication is false: a reversible deterministic process on a finite state space can contain cycles, and in the described mechanics a laser can be trapped in a closed loop by an arrangement of mirrors. Therefore the claim that every shot terminates in fewer than 4n steps is not established, and the proof that LaserTank is in NP fails as written. A correct argument would need to track the directed state of the ray and stop when a state repeats; since there are only O(n) distinct directed states, a terminating shot is a simple path of length O(n), while a repeated state certifies nontermination.
[Abstract and Section 2.1 / closing remark] The abstract and Theorem 1 state that NP-completeness holds even when the only blocks on the board are mirrors and solid blocks, but the reduction as presented uses movable blocks in the literal and AND gadgets (Figures 1a and 1c). The closing remark, which claims that movable blocks can be replaced by ◸-mirrors without changing behavior, is not proved. Because the informal correctness argument for the AND gadget explicitly relies on movable blocks being pushed, this claim is load-bearing for the advertised restricted version of the theorem. The authors must either provide a proof of the replacement claim or restate the theorem to allow movable blocks.
[Section 2, gadget descriptions and Figures 1a-1d] The correctness of the reduction rests on informal assertions that each gadget enforces the intended boolean behavior. In particular, the AND-gadget claim that the movable block can only be moved up, right, and down, and that it must be moved right by activation from both inputs, does not rule out alternative laser paths or sequences of pushes that might unlock the output without both inputs being available. A rigorous proof needs a full case analysis of all possible interactions in each gadget, including shots that hit mirrors from unintended sides and blocks that are pushed in unintended orders. Without such an analysis, the claimed equivalence between puzzle solvability and formula satisfiability is not fully established.

minor comments (4)

[Throughout] There are several typographical errors, such as 'Insitute' for 'Institute' and 'Swed en' for 'Sweden' in the author affiliations.
[Section 2, notation] The notation for gadget inputs and outputs in the figures is not defined precisely; for example, ⤑, ⤑*, and the labels A, B, C are used informally and should be explained with a legend.
[Proof of Theorem 1] The statement 'one may simply let these values be true' for variables whose truth value is not decided by a puzzle solution needs justification: the authors should show that any solution to the constructed puzzle yields a satisfying assignment regardless of which variables remain undecided.
[Section 2, laser mechanics] The sentence 'the laser stops as soon as it hits a solid block, a movable block, or moves a mirror' should clarify that a laser hitting a mirror on a reflective edge is reflected, not stopped, and that 'moves a mirror' refers to pushing it via a non-reflective short edge.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained polynomial-time reduction from 3-SAT, an externally established NP-complete problem.

full rationale

The paper's central claim is that LaserTank is NP-complete, established by a direct reduction from 3-SAT. The reduction constructs explicit gadgets and gives a polynomial bound on the board size in terms of the number of variables and clauses. The NP-hardness direction rests on the standard Cook-Levin result for 3-SAT, cited as [1], which is independent of this paper and not authored by the present authors. The membership-in-NP direction relies on Lemma 1, which asserts a polynomial-time verification of a solution. That lemma contains a correctness flaw: the argument that time-reversibility rules out infinite loops is false, since reversible finite-state systems can have cycles. However, this is a mathematical error in the proof of the lemma, not a circularity; the claimed verification bound is not being derived from the target result or from a self-citation. The paper does not fit any parameters to data, does not rename an empirical pattern as a prediction, and does not invoke the authors' prior results as load-bearing support. The only citations are to external complexity-theory results (Cook, Sokoban, Tetris, Rush Hour, Minesweeper) and a general framework paper by Viglietta, which is mentioned only as an optional alternative approach and is not used in the proof. Therefore no derivation step reduces to its own input by construction, and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities are introduced. The reduction depends only on the NP-completeness of 3-SAT, the declared game mechanics, and the faulty termination assumption in Lemma 1. The latter is a concrete weakness in the proof.

assumptions (3)

standard math 3-SAT is NP-complete (Cook-Levin theorem), used as the source problem for the reduction.
Invoked in the proof of Theorem 1 as the known hard problem that the reduction starts from.
domain assumption The game rules defined in Section 2 (laser reflection, pushing, solid blocks, goal condition) accurately describe the studied variant of LaserTank.
The entire reduction is built on these mechanics; any change in rules could break the gadgets.
ad hoc to paper Each laser shot terminates in O(n) steps because laser movement is time-reversible and thus loop-free.
This is asserted in Lemma 1; the reversibility argument is incorrect because reversible systems can cycle, so this assumption is unjustified as stated. A fix would be to detect repeated states during simulation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of LaserTank is NP-complete." pith.science (2026). https://pith.science/paper/E2KP764U

@misc{pith2026190805966,
  author       = {Pith},
  title        = {Pith review of: LaserTank is NP-complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/E2KP764U}},
  note         = {Machine review of arXiv:1908.05966}
}

abstract

We show that the classical game LaserTank is $\mathrm{NP}$-complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mirrors and solid blocks. We show this by reducing $3$-SAT instances to LaserTank puzzles.

Figures

Figures reproduced from arXiv: 1908.05966 by the authors.

**Figure 1.** The and-gadget, three-or-gadget, literal-gadget, and switch-gadget. The three-or gadget is depicted in Figure 1b. If either of the inputs , or are available, then allows for output. The only way to produce output from is to move a ◸ to the same row as . The ◸ can only be moved into that row from above and thus we must have some input from , or in order for a laser to pass out through . Thus the three-or gadget works… view at source ↗

**Figure 2.** Left: A small puzzle showing the use of two switch-gadgets and one and-gadget. Right: Layout of a general 3-SAT puzzle. Above each or-gadget are three switches, corresponding to the three literals involved on the or-clause. The following lemma shows that solving LaserTank puzzles can be done in polynomial time with a non-deterministic Turing machine. Hence LaserTank is in NP. Lemma 1. A solution consisting of steps… view at source ↗

**Figure 3.** The puzzle corresponding to the expression ( ∨ ∨ ¬) ∧ ( ∨ ¬ ∨ ). Note that if = , the expression is satisfied. Thus this particular puzzle can be solved without deciding truth values for the variables and , and the movable blocks in the and variable gadgeds do not need to be moved. valid even in the case when restricting to puzzles without movable blocks. Furthermore, we can extend Theorem 1 to the case where the ta… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

8 extracted references · 5 canonical work pages

[1]

In: Proceedings of the Third Annual ACM Symposium on Theory of Computing

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151--158. STOC '71, ACM, New York, NY, USA (1971). doi:10.1145/800157.805047

arXiv 1971
[2]

Computational Geometry 13(4), 215--228 (Oct 1999)

Dor, D., Zwick, U.: SOKOBAN and other motion planning problems. Computational Geometry 13(4), 215--228 (Oct 1999). doi:10.1016/s0925-7721(99)00017-6

work page doi:10.1016/s0925-7721(99)00017-6 1999
[3]

Tetris is Hard, Even to Approximate

Erik D. Demaine, S.H., Liben-Nowell, D.: Tetris is hard, even to approximate. Tech. Rep. MIT-LCS-TR-865, MIT, Cambridge (2002), https://arxiv.org/abs/cs/0210020

work page Pith review arXiv 2002
[4]

Theoretical Computer Science 270(1-2), 895--911 (Jan 2002)

Flake, G.W., Baum, E.B.: R ush H our is PSPACE -complete, or `` W hy you should generously tip parking lot attendants''. Theoretical Computer Science 270(1-2), 895--911 (Jan 2002). doi:10.1016/s0304-3975(01)00173-6

work page doi:10.1016/s0304-3975(01)00173-6 2002
[5]

The Mathematical Intelligencer 22(2), 9--15 (Mar 2000)

Kaye, R.: Minesweeper is NP -complete. The Mathematical Intelligencer 22(2), 9--15 (Mar 2000). doi:10.1007/bf03025367

work page doi:10.1007/bf03025367 2000
[6]

doi:10.1007/s00224-013-9497-5

Viglietta, G.: Gaming is a hard job, but someone has to do it! Theory of Computing Systems 54(4), 595--621 (Aug 2013). doi:10.1007/s00224-013-9497-5

work page doi:10.1007/s00224-013-9497-5 2013
[7]

, " * write output.state after.block = add.period write

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 'after.sentence := #3 '...
[8]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

In: Proceedings of the Third Annual ACM Symposium on Theory of Computing

Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151--158. STOC '71, ACM, New York, NY, USA (1971). doi:10.1145/800157.805047

arXiv 1971

[2] [2]

Computational Geometry 13(4), 215--228 (Oct 1999)

Dor, D., Zwick, U.: SOKOBAN and other motion planning problems. Computational Geometry 13(4), 215--228 (Oct 1999). doi:10.1016/s0925-7721(99)00017-6

work page doi:10.1016/s0925-7721(99)00017-6 1999

[3] [3]

Tetris is Hard, Even to Approximate

Erik D. Demaine, S.H., Liben-Nowell, D.: Tetris is hard, even to approximate. Tech. Rep. MIT-LCS-TR-865, MIT, Cambridge (2002), https://arxiv.org/abs/cs/0210020

work page Pith review arXiv 2002

[4] [4]

Theoretical Computer Science 270(1-2), 895--911 (Jan 2002)

Flake, G.W., Baum, E.B.: R ush H our is PSPACE -complete, or `` W hy you should generously tip parking lot attendants''. Theoretical Computer Science 270(1-2), 895--911 (Jan 2002). doi:10.1016/s0304-3975(01)00173-6

work page doi:10.1016/s0304-3975(01)00173-6 2002

[5] [5]

The Mathematical Intelligencer 22(2), 9--15 (Mar 2000)

Kaye, R.: Minesweeper is NP -complete. The Mathematical Intelligencer 22(2), 9--15 (Mar 2000). doi:10.1007/bf03025367

work page doi:10.1007/bf03025367 2000

[6] [6]

doi:10.1007/s00224-013-9497-5

Viglietta, G.: Gaming is a hard job, but someone has to do it! Theory of Computing Systems 54(4), 595--621 (Aug 2013). doi:10.1007/s00224-013-9497-5

work page doi:10.1007/s00224-013-9497-5 2013

[7] [7]

, " * write output.state after.block = add.period write

ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 'after.sentence := #3 '...

[8] [8]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...