On problems as hard as CNF-SAT

M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh, M. Wahlström

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

66 Citaten (Scopus)
1 Downloads (Pure)


The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including Graph Coloring, Hamiltonian Path, Dominating Set and 3-CNF-Sat. In some instances, improving these algorithms further seems to be out of reach. The CNF-Sat problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2^n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-Sat that run in time o(2^n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon
Originele taal-2Engels
Titel27th Conference on Computational Complexity (CCC'12, Porto, Portugal, June 26-29, 2012)
Plaats van productieWashington D.C.
UitgeverijIEEE Computer Society
ISBN van geprinte versie978-0-7695-4708-4
StatusGepubliceerd - 2012
Extern gepubliceerdJa
Evenementconference; 27th Conference on Computational Complexity -
Duur: 1 jan. 2012 → …


Congresconference; 27th Conference on Computational Complexity
Periode1/01/12 → …
Ander27th Conference on Computational Complexity


Duik in de onderzoeksthema's van 'On problems as hard as CNF-SAT'. Samen vormen ze een unieke vingerafdruk.

Citeer dit