Impagliazzo–Paturi–Zane's Strong Exponential Time Hypothesis

At least 1 year old · documented by

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 q≥3q\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.