Cover Image

Complexity of 2D Snake Cube Puzzles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	MIT Hardness Group, Anchaleenukoon, Nithid, Dang, Alex, Demaine, Erik D., Ji, Kaylee, Saengrungkongka, Pitchayut
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tetris with Few Piece Types
by: MIT Hardness Group, et al.
Published: (2024)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
by: MIT Hardness Group, et al.
Published: (2024)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
by: MIT Hardness Group, et al.
Published: (2026)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
by: MIT Hardness Group, et al.
Published: (2025)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
by: Gajjar, Kshitij, et al.
Published: (2026)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

Gluing Genus 1 and Genus 2 Curves Along $\ell$-torsion
by: Saengrungkongka, Pitchayut, et al.
Published: (2025)

The Complexity of Drawing Graphs on Few Lines and Few Planes
by: Chaplick, Steven, et al.
Published: (2016)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Complexity of Contextuality
by: Yianni, Theodoros, et al.
Published: (2025)

Computational Complexities of Folding
by: Eppstein, David
Published: (2024)

Tiling with Three Polygons is Undecidable
by: Demaine, Erik D., et al.
Published: (2024)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

On Saxe's theorems about the complexity of the Distance Geometry Problem
by: Kupperschmitt, Maël, et al.
Published: (2025)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

Geometric Bipartite Matching is in NC
by: Bhore, Sujoy, et al.
Published: (2024)

Constrained Boundary Labeling
by: Depian, Thomas, et al.
Published: (2024)

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

Minimum Selective Subset on Some Graph Classes
by: Manna, Bubai
Published: (2025)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Counting Triangulations of Fixed Cardinal Degrees
by: Chambers, Erin, et al.
Published: (2025)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)

Query-Efficient Fixpoints of $\ell_p$-Contractions
by: Haslebacher, Sebastian, et al.
Published: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
by: Gibor, Daniel
Published: (2025)

On the hardness of finding normal surfaces
by: Burton, Benjamin A., et al.
Published: (2019)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
by: Boomari, Hossein, et al.
Published: (2018)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
by: Manna, Bubai
Published: (2025)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
by: Takahata, Takuma, et al.
Published: (2025)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

Extremal $t$-intersecting Families of Permutations for Large $t$
by: Saengrungkongka, Pitchayut
Published: (2026)