← All problems

Strong Exponential Time Hypothesis

Let sks_k be the infimum of constants cc such that kk-SAT on nn variables is solvable in time O(2cn)O(2^{cn}) up to polynomial factors.

Is limksk=1\lim_{k\to\infty}s_k=1?

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li