| ▲ | csheehan10 4 hours ago | |
To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1. In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n. | ||
| ▲ | csheehan10 4 hours ago | |
To achieve this you would need to show that 3SAT is solvable in 2^{n^c} time for every c>0, not just a single c<1. In this case they have c = 1-0.5(\log \log n)/(\log n) which is approaching 1 for large n. | ||