A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem

DOI10.3390/a5020261zbMath1461.68089MaRDI QIDQ1736511

Kenichi Morita, Chuzo Iwamoto, Kento Sasaki

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/e72f9aa5bf9023a66f80ade4613968c0e2415526

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68R07: Computational aspects of satisfiability