A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
From MaRDI portal
Publication:1736511
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
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R07: Computational aspects of satisfiability