On Super Strong ETH
Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2[superscript n(1-1/O(k))] time algorithm for k-SAT in the worst case. For this reason, it has been hypothesized that the worst-case k-SAT problem cannot be solved in 2[superscript n(1-f(k)/k)] t...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
AI Access Foundation
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129796 |