All Questions
1 question
47
votes
0
answers
1k
views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
- 3,722