Exponential time hypothesis
Does solving 3-SAT really require exponential time?
Summary
The hypothesis that 3-SAT cannot be solved in subexponential time is unproven; if true, it would imply P ≠ NP and that many known algorithms are close to optimal.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.
