A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem (Q1736511): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2157125666 / rank | |||
Normal rank |
Latest revision as of 22:15, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem |
scientific article |
Statements
A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem (English)
0 references
26 March 2019
0 references
Summary: 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 \(f\) of the 3SAT problem to a string puzzle \(s\) such that \(f\) is satisfiable if and only if \(s\) is solvable. Therefore, the generalized string puzzle problem is NP-hard.
0 references