Results on a Super Strong Exponential Time Hypothesis
<jats:p>All known SAT-solving paradigms (backtracking, local search, and the polynomial method) only yield a 2n(1−1/O(k)) time algorithm for solving k-SAT in the worst case, where the big-O constant is independent of k. For this reason, it has been hypothesized that k-SAT cannot be solved in w...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for the Advancement of Artificial Intelligence (AAAI)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143932 |