Impagliazzo–Paturi–Zane's Strong Exponential Time Hypothesis

From papers

Let qq-CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most qq literals, and let nn be the number of variables in the input formula. Strong Exponential Time Hypothesis. There is no ϵ>0\epsilon>0 such that, for every q3q\geq 3, qq-CNFSAT can be solved in (2ϵ)nnO(1)(2-\epsilon)^n n^{\mathcal{O}(1)} time. The hypothesis is a standard basis for fine-grained lower bounds; the source invokes it to prove one of its lower bounds, and no resolution status is given here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pradeesha Ashok, Gautam K. Das, Arti Pandey, Kaustav Paul and Subhabrata Paul, “(Independent) Roman Domination Parameterized by Distance to Cluster”, arXiv:2411.13141 (2024).

Solutions 0

No solutions have been posted yet.