3-SAT → Tiles without teleport moves Complexity open
Unsolved
Why this question matters
Removing teleportation tests whether local feature transitions alone create hardness in the puzzle model.
Hardness that relies on teleport moves does not settle the local-movement-only rules used here.
The reduction to construct
A source instance is an explicitly encoded Boolean formula with at most three literals per clause. Its outputs are satisfying Boolean assignments, or NO-SOLUTION when the formula is unsatisfiable.
Tiles carry finite feature sets. Consecutive chosen tiles must share a currently present feature; moving deletes their common features. The goal is to remove all features, with no teleport or zero-effect moves.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
A reduction must enforce movement and deletion together, without relying on forbidden jumps.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
- Man, These New York Times Games Are Hard! A Computational Perspective ↗
- full arXiv version ↗
- version history ↗
Literature checked 2026-09-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.