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

DOI10.3390/a5020261zbMath1461.68089OpenAlexW2157125666MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

This page was built for publication: A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem