SETH — гипотеза, утверждающая, что $ \forall \epsilon > 0 $ задачу SAT нельзя решить за время $ O^*((2-\epsilon)^{n}) $, где $ n $ — количество переменных. Так как SAT можно свести к другим $ NP $-трудным задачам, из SETH следуют и некоторые нижние оценки на время решения этих задач.

Оказывается, что из SETH можно вывести и нижние оценки на время решения некоторых задач, зависящих от параметра. Например, из SETH следует, что задачу Dominating Set $ \forall \epsilon > 0 $ нельзя решить за время $ O^*((3-\epsilon)^{tw(G)}) $ ($ tw(G) $ — древесная ширина графа $ G $). Для доказательства подобных фактов можно, например, найти такое сведение SAT к нужной задаче, которое бы приводило к инстансам задачи с небольшим значением параметра. Доклад посвящён таким сведениям для нескольких известных задач, параметризованных древесной шириной. Выведенные таким образом нижние оценки уже достигнуты существующими алгоритмами. Отсюда следует, что если эти алгоритмы удастся улучшить, то и для SAT будет немедленно получен более быстрый алгоритм.