「Finding a Hamiltonian Path in a Cube with Specified Turns is Hard」
Finding a Hamiltonian Path in a Cube with Specified Turns is Hard
［Journal of Information Processing Vol.21 No.3, pp.368-377］
We prove the NP-completeness of finding a Hamiltonian path in an N × N × N cube graph with turns exactly at specified lengths along the path. This result establishes NP-completeness of Snake Cube puzzles: folding a chain of N3 unit cubes, joined at face centers (usually by a cord passing through all the cubes), into an N × N × N cube. Along the way, we prove a universality result that zig-zag chains (which must turn every unit) can fold into any polycube after 4 × 4 × 4 refinement, or into any Hamiltonian polycube after 2 × 2 × 2 refinement.
Zachary Abel is a Ph.D. candidate in the Department of Applied Mathematics at the Massachusetts Institute of Technology (MIT) working with Professor Erik D. Demaine in the Computer Science and Artificial Intelligence Lab (CSAIL). His primary research is in computational and discrete geometry, including such topics as computational origami and geometric rigidity theory. Mr. Abel is currently funded under the National Science Foundation (NSF) Graduate Research Fellowship Program, and he received his Bachelors of Arts in Mathematics and Computer Science from Harvard in 2010.
Erik D. Demaine received a B.Sc. degree from Dalhousie University in 1995, and M.Math. and Ph.D. degrees from University of Waterloo in 1996 and 2001, respectively. Since 2001, he has been a professor in computer science at the Massachusetts Institute of Technology. His research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games. In 2003, he received a MacArthur Fellowship as a “computational geometer tackling and solving difficult problems related to folding and bending—moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter”. He cowrote a book about the theory of folding, together with Joseph O’Rourke (Geometric Folding Algorithms, 2007), and a book about the computational complexity of games, together with Robert Hearn (Games, Puzzles, and Computation, 2009).
Martin L. Demaine is an artist and mathematician. He started the first private hot glass studio in Canada and has been called the father of Canadian glass. Since 2005, he has been the Angelika and Barton Weller Artist-in-Residence at the Massachusetts Institute of Technology. Both Martin and Erik work together in paper, glass, and other material. They use their exploration in sculpture to help visualize and understand unsolved problems in mathematics, and their scientific abilities to inspire new art forms. Their artistic work includes curved origami sculptures in the permanent collections of the Museum of Modern Art (MoMA) in New York, and the Renwick Gallery in the Smithsonian. Their scientific work includes over 60 published joint papers, including several about combining mathematics and art.
Sarah Eisenstat is a Ph.D. student in the Department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, working with Professor Erik D. Demaine. Her current research interests include computational geometry and algorithms. She received her Sc.B. and Sc.M. degrees from Brown University in 2008 and 2009, respectively.
Jayson Lynch received his B.Sc. in Physics and Computer Science from MIT in 2013 and remains there as a Ph.D. candidate in the Department of Electrical Engineering and Computer Science working with Professor Erik D. Demaine. His research interests include algorithms, computational geometry, and the interplay between physics and computation.
Tao B. Schardl is a Ph.D. candidate in the Department of Electrical Engineering and Computer Science (EECS) at the Massachusetts Institute of Technology (MIT). He is a member of MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), and works in the Supertech group with Professor Charles Leiserson. His primary research is on developing parallel algorithms and parallel data structures. His previous research includes developing a work-efficient parallel breadth-first search algorithm, designing a theoretical framework for analyzing Cilk programs with nonconstant-time reducer hyperobjects, and developing mechanisms to support deterministic parallel random-number generation. Mr. Schardl received his Bachelor of Science in Computer Science and Electrical Engineering from MIT in 2009 and his Masters of Engineering in Computer Science and Electrical Engineering from MIT in 2010.