a polynomial-time reduction from the 3sat problem to the generalized string puzzle problem多项式时间减少3 sat问题的广义字符串难题问题.pdfVIP

Algorithms 2012, 5, 261-272; doi:10.3390/a5020261 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article A Polynomial-Time Reduction from the 3SAT Problem to the Generalized String Puzzle Problem Chuzo Iwamoto *, Kento Sasaki and Kenichi Morita Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima, 739-8527 Japan; E-Mails: ksasaki@iec.hiroshima-u.ac.jp (K.S.); km@hiroshima-u.ac.jp (K.M.) ⋆ Author to whom correspondence should be addressed; E-Mail: chuzo@hiroshima-u.ac.jp; Tel.: +81-82-424-7702; Fax: +81-82-424-7702. Received: 11 November 2011; in revised form: 27 February 2012 / Accepted: 7 April 2012 / Published: 13 April 2012 Abstract: A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one piece from another set of pieces. A string puzzle consists of strings entangled with one or more wooden pieces. We consider the generalized string puzzle problem whose input is the layout of strings and a wooden board with holes embedded in the 3-dimensional Euclidean space. We present a polynomial-time transformation from an arbitrary instance of the 3SAT problem to a string puzzle such that is satisfiable if and only if is solvable. Therefore, the generalized string puzzle problem is NP-hard. Keywords: disentanglement puzzle; polynomial-time reduction; NP-hard 1. Introduction A disentanglement puzzle consists of mechanically interlinked pieces, and the puzzle is solved by disentangling one pi