2015 | OriginalPaper | Buchkapitel
Lower Bounds Based on the Exponential-Time Hypothesis
verfasst von : Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Exponential Time Hypothesis (ETH) is a conjecture stating that, roughly speaking, n
-
variable
3-SAT
cannot be solved in time
2
o
(
n
)
. In this chapter, we prove lower bounds based on ETH for the time needed to solve various problems. In many cases, these lower bounds match (up to small factors) the running time of the best known algorithms for the problem.