A - Sliding Block PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation. May 2002. arXiv:0205005. https://arxiv.org/abs/cs/0205005 B - Gaming Gaming Is a Hard Job, but Someone Has to Do It! 2014. TOCS Oct 2013. arXiv:1201.4995. https://arxiv.org/abs/1201.4995 C - Set The Computational Complexity of the Game of Set and its Theoretical Applications. Jun 2014. LATIN 2014. D - Nintendo (U) Classic Nintendo Games are (Computationally) Hard. Feb 2015. arXiv:1203.1895. https://arxiv.org/abs/1203.1895 E - Harder Mario (U) Super Mario Bros. Is Harder/Easier than We Thought. Jun 2016. FUN 2016 F - Portal (U) The Computational Complexity of Portal and Other 3D Video Games. Nov 2016. arXiv:1611.10319. https://arxiv.org/abs/1611.10319 G - 1N Edge (U) Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard. Dec 2016. arXiv:1701.00146. https://arxiv.org/abs/1701.00146 H - Quantum (U) Toward Quantum Combinatorial Games. Jan 2017. HAL:hal-01429072. https://hal.archives-ouvertes.fr/hal-01429072 or arXiv:1701.02193 https://arxiv.org/abs/1701.02193v2 I - Optimal Cubes (U) Solving the Rubik’s Cube Optimally is NP-complete. Jun 2017. arXiv:1706.06708. https://arxiv.org/abs/1706.06708 J - Motion Planning Computational Complexity of Motion Planning of a Robot through Simple Gadgets. Jun 2018. FUN 2018. arXiv:1806.03539. https://arxiv.org/abs/1806.03539 K - Towards Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard. Dec 2018. arXiv:1812.03592. https://arxiv.org/abs/1812.03592 L - Tilt Hierarchical Shape Construction and Complexity for Slidable Polyominoes under Uniform External Forces. Jan 2020. SODA 2020. M - Edge Matching Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players. Feb 2020. arXiv:2002.03887. https://arxiv.org/abs/2002.03887 N - Rush Hour 1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete. Mar 2020. arXiv:2003.09914. https://arxiv.org/abs/2003.09914 O - Trains Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets. May 2020. WALCOM 2022. arXiv:2005.03192. https://arxiv.org/abs/2005.03192 P - Doors Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets. Jun 2020. arXiv:2006.01256. https://arxiv.org/abs/2006.01256 Q - Tetris (U) Tetris is NP-hard even with O(1) rows or columns. Sep 2020. arXiv:2009.14336. https://arxiv.org/abs/2009.14336 R - FPT Fixed-Parameter Algorithms for Graph Constraint Logic. Nov 2020. arXiv:2011.10385. https://arxiv.org/abs/2011.10385 W - MP-3SAT-NVP On Two-Handed Planar Assembly Partitioning. Jan 2021. SODA 2021 https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.105 S - Dots Dots & Boxes is PSPACE-complete. May 2021. arXiv:2105.02837. https://arxiv.org/abs/2105.02837 T - Compacting Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. Dec 2021. arXiv:2105.07997. https://arxiv.org/abs/2105.07997 U - Reconfiguration Traversability, Reconfiguration, and Reachability in the Gadget Framework. May 2022. WALCOM 2022. V - Barrier Barrier-1 Reachability for Thermodynamic Binding Networks is PSPACE-complete. Jan 2022. preprint ORDER Standard Hardness Reductions -D Nintendo (U) - U3 -B Gaming - G4 -C Set - G4 -E Harder Mario (U) - U2 -G 1N Edge (U) - G2 -I Optimal Cubes (U) G7 -M Edge Matching - G5 -Q Tetris (U) - G8 -W MP-3SAT-NVP - G6 -S Dots - G9 -T Compacting - G2 Constraint Logic -A Sliding Block U4 -F Portal (U) -L Tilt - G7 -N Rush Hour - G5 -V Barrier - G6 -R FPT - G8 -Gadget Motion Planning Framework --J Motion Planning - G3 --K Towards - G3 --O Trains - U1 --P Doors - G9 --U Reconfiguration - G1 Quantum -H Quantum (U) - G1 Reference -Hearn's Thesis -Lynch's Thesis