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 |
| _version_ | 1826205704488222720 |
|---|---|
| author | Vyas, Nikhil Williams, Ryan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Vyas, Nikhil Williams, Ryan |
| author_sort | Vyas, Nikhil |
| collection | MIT |
| description | <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 worst-case 2n(1−f(k)/k) time, for any unbounded ƒ : ℕ → ℕ. This hypothesis has been called the “Super-Strong Exponential Time Hypothesis” (Super Strong ETH), modeled after the ETH and the Strong ETH. We prove two results concerning the Super-Strong ETH:1. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is 2k ln 2 −Θ(1). We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. In particular, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2n(1−Ω( log k)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1998).2. The Unique k-SAT problem is the special case where there is at most one satisfying assignment. It is natural to hypothesize that the worst-case (exponential-time) complexity of Unique k-SAT is substantially less than that of k-SAT. Improving prior reductions, we show the time complexities of Unique k-SAT and k-SAT are very tightly related: if Unique k-SAT is in 2n(1−f(k)/k) time for an unbounded f, then k-SAT is in 2n(1−f(k)(1−ɛ)/k) time for every ɛ > 0. Thus, refuting Super Strong ETH in the unique solution case would refute Super Strong ETH in general.</jats:p> |
| first_indexed | 2024-09-23T13:17:16Z |
| format | Article |
| id | mit-1721.1/143932 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:17:16Z |
| publishDate | 2022 |
| publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| record_format | dspace |
| spelling | mit-1721.1/1439322023-01-20T18:08:34Z Results on a Super Strong Exponential Time Hypothesis Vyas, Nikhil Williams, Ryan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science <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 worst-case 2n(1−f(k)/k) time, for any unbounded ƒ : ℕ → ℕ. This hypothesis has been called the “Super-Strong Exponential Time Hypothesis” (Super Strong ETH), modeled after the ETH and the Strong ETH. We prove two results concerning the Super-Strong ETH:1. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is 2k ln 2 −Θ(1). We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. In particular, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2n(1−Ω( log k)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1998).2. The Unique k-SAT problem is the special case where there is at most one satisfying assignment. It is natural to hypothesize that the worst-case (exponential-time) complexity of Unique k-SAT is substantially less than that of k-SAT. Improving prior reductions, we show the time complexities of Unique k-SAT and k-SAT are very tightly related: if Unique k-SAT is in 2n(1−f(k)/k) time for an unbounded f, then k-SAT is in 2n(1−f(k)(1−ɛ)/k) time for every ɛ > 0. Thus, refuting Super Strong ETH in the unique solution case would refute Super Strong ETH in general.</jats:p> 2022-07-21T15:56:32Z 2022-07-21T15:56:32Z 2020 2022-07-21T15:50:09Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/143932 Vyas, Nikhil and Williams, Ryan. 2020. "Results on a Super Strong Exponential Time Hypothesis." Proceedings of the AAAI Conference on Artificial Intelligence, 34 (09). en 10.1609/AAAI.V34I09.7125 Proceedings of the AAAI Conference on Artificial Intelligence Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for the Advancement of Artificial Intelligence (AAAI) Association for the Advancement of Artificial Intelligence (AAAI) |
| spellingShingle | Vyas, Nikhil Williams, Ryan Results on a Super Strong Exponential Time Hypothesis |
| title | Results on a Super Strong Exponential Time Hypothesis |
| title_full | Results on a Super Strong Exponential Time Hypothesis |
| title_fullStr | Results on a Super Strong Exponential Time Hypothesis |
| title_full_unstemmed | Results on a Super Strong Exponential Time Hypothesis |
| title_short | Results on a Super Strong Exponential Time Hypothesis |
| title_sort | results on a super strong exponential time hypothesis |
| url | https://hdl.handle.net/1721.1/143932 |
| work_keys_str_mv | AT vyasnikhil resultsonasuperstrongexponentialtimehypothesis AT williamsryan resultsonasuperstrongexponentialtimehypothesis |