Impagliazzo–Paturi–Zane's Strong Exponential Time Hypothesis
Impagliazzo–Paturi–Zane's Strong Exponential Time Hypothesis
Let -CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most literals, and let be the number of variables in the input formula. Strong Exponential Time Hypothesis. There is no such that, for every , -CNFSAT can be solved in 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
Sign in to submit a solution.
No solutions have been posted yet.