weak_exponential_time_hypothesis (402B)
1 # Weak exponential time hypothesis 2 3 The [computational_hypothesis] that we cannot solve [3-SAT] in time 2^{o(n)} 4 5 Implied by [exponential_time_hypothesis] but not equivalent 6 - cf https://en.wikipedia.org/wiki/Exponential_time_hypothesis 7 - indeed you could have algorithms in 2^{delta n} for every delta > 0, that get more and more complicated, and none for delta = 0 8 9 Up: [exponential_time_hypothesis]