On Problems as Hard as CNF-SAT

DOI10.1145/2925416zbMath1442.68064arXiv1112.2275MaRDI QIDQ4962605

Ramamohan Paturi, Marek Cygan, Saket Saurabh, Daniel Lokshtanov, Dániel Marx, Yoshio Okamoto, Magnus Wahlström, Holger Dell, Jesper Nederlof

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.2275

zbMATH Keywords

reduction; satisfiability; strong exponential-time hypothesis; optimal growth rate

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

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

68R07: Computational aspects of satisfiability