For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
NP-Hard and k-EXPSPACE-Hard Cast Puzzles
Chuzo IWAMOTO Kento SASAKI Kenji NISHIO Kenichi MORITA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/11/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
computational complexity, NP-hard, k-EXPSPACE hard, cast puzzle,
Full Text: PDF(645.8KB)>>
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.