NP-Hard and k-EXPSPACE-Hard Cast Puzzles

Chuzo IWAMOTO  Kento SASAKI  Kenji NISHIO  Kenichi MORITA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.11   pp.2995-3004
Publication Date: 2010/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.2995
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
computational complexity,  NP-hard,  k-EXPSPACE hard,  cast puzzle,  

Full Text: PDF(645.8KB)>>
Buy this Article




Summary: 
A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one piece from another set of pieces. A cast puzzle is a type of disentanglement puzzle, where each piece is a zinc die-casting alloy. In this paper, we consider the generalized cast puzzle problem whose input is the layout of a finite number of pieces (polyhedrons) in the 3-dimensional Euclidean space. For every integer k ≥ 0, we present a polynomial-time transformation from an arbitrary k-exponential-space Turing machine M and its input x to a cast puzzle c1 of size k-exponential in |x| such that M accepts x if and only if c1 is solvable. Here, the layout of c1 is encoded as a string of length polynomial (even if c1 has size k-exponential). Therefore, the cast puzzle problem of size k-exponential is k-EXPSPACE-hard for every integer k ≥ 0. We also present a polynomial-time transformation from an arbitrary instance f of the SAT problem to a cast puzzle c2 such that f is satisfiable if and only if c2 is solvable.