Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds
In this thesis we study satisfiability algorithms and connections between algorithms and circuit lower bounds. We give new results in the following three areas: Oracles and Algorithmic Methods for Proving Lower Bounds: We give an equivalence between relativizing circuit lower bounds (circuit lowe...
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Médium: | Diplomová práce |
| Vydáno: |
Massachusetts Institute of Technology
2023
|
| On-line přístup: | https://hdl.handle.net/1721.1/150213 https://orcid.org/0000-0002-4055-7693 |
| _version_ | 1826198284016812032 |
|---|---|
| author | Vyas, Nikhil |
| author2 | Williams, R. Ryan |
| author_facet | Williams, R. Ryan Vyas, Nikhil |
| author_sort | Vyas, Nikhil |
| collection | MIT |
| description | In this thesis we study satisfiability algorithms and connections between algorithms and circuit lower bounds. We give new results in the following three areas:
Oracles and Algorithmic Methods for Proving Lower Bounds: We give an equivalence between relativizing circuit lower bounds (circuit lower bounds which hold with respect to all oracles) and the existence of uniform circuits for a problem we call the MISSING-STRING problem. This connection allows us to (a) prove new time hierarchy results and (b) reduce various open problems such as whether there exists an oracle B such that [formula] to circuit lower bounds for the MISSING-STRING problem. We also give new oracles which show that the "algorithms to lower bounds" framework of Williams does not relativize.
Circuit Lower Bounds from #SAT Algorithms: Williams' paradigm for lower bounds gives circuit lower bounds from circuit satisfiability algorithms. We build upon this paradigm and study lower bounds that can be obtained from algorithms which count the number of satisfying solutions for a circuit i.e. #SAT algorithms. Informally, we show that #SAT algorithms for circuit class C imply lower bounds for the class of functions which can be written as “sparse symmetric” functions of C. This allows us to show that NQP (nondeterministic quasi-polynomial time) is not contained in the class of [formula] circuits.
Complexity of k-SAT and its variants: k-SAT is a canonical NP-complete problem for k ≥ 3 and tremendous effort has been devoted to finding faster algorithms for it and to understand its complexity. We study the time complexity of k-SAT and its variants such as average-case k-SAT and Unique k-SAT. We give new algorithms for various average case variants of k-SAT that are faster than the best known algorithms for worst case k-SAT. We also give a fine grained reduction from k-SAT to Unique k-SAT which shows that their time complexities are tightly linked. |
| first_indexed | 2024-09-23T11:02:27Z |
| format | Thesis |
| id | mit-1721.1/150213 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:02:27Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1502132023-04-01T03:42:20Z Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds Vyas, Nikhil Williams, R. Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science In this thesis we study satisfiability algorithms and connections between algorithms and circuit lower bounds. We give new results in the following three areas: Oracles and Algorithmic Methods for Proving Lower Bounds: We give an equivalence between relativizing circuit lower bounds (circuit lower bounds which hold with respect to all oracles) and the existence of uniform circuits for a problem we call the MISSING-STRING problem. This connection allows us to (a) prove new time hierarchy results and (b) reduce various open problems such as whether there exists an oracle B such that [formula] to circuit lower bounds for the MISSING-STRING problem. We also give new oracles which show that the "algorithms to lower bounds" framework of Williams does not relativize. Circuit Lower Bounds from #SAT Algorithms: Williams' paradigm for lower bounds gives circuit lower bounds from circuit satisfiability algorithms. We build upon this paradigm and study lower bounds that can be obtained from algorithms which count the number of satisfying solutions for a circuit i.e. #SAT algorithms. Informally, we show that #SAT algorithms for circuit class C imply lower bounds for the class of functions which can be written as “sparse symmetric” functions of C. This allows us to show that NQP (nondeterministic quasi-polynomial time) is not contained in the class of [formula] circuits. Complexity of k-SAT and its variants: k-SAT is a canonical NP-complete problem for k ≥ 3 and tremendous effort has been devoted to finding faster algorithms for it and to understand its complexity. We study the time complexity of k-SAT and its variants such as average-case k-SAT and Unique k-SAT. We give new algorithms for various average case variants of k-SAT that are faster than the best known algorithms for worst case k-SAT. We also give a fine grained reduction from k-SAT to Unique k-SAT which shows that their time complexities are tightly linked. Ph.D. 2023-03-31T14:40:02Z 2023-03-31T14:40:02Z 2023-02 2023-02-28T14:39:51.338Z Thesis https://hdl.handle.net/1721.1/150213 https://orcid.org/0000-0002-4055-7693 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Vyas, Nikhil Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title | Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title_full | Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title_fullStr | Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title_full_unstemmed | Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title_short | Satisfiability Algorithms and Connections between Algorithms and Circuit Lower Bounds |
| title_sort | satisfiability algorithms and connections between algorithms and circuit lower bounds |
| url | https://hdl.handle.net/1721.1/150213 https://orcid.org/0000-0002-4055-7693 |
| work_keys_str_mv | AT vyasnikhil satisfiabilityalgorithmsandconnectionsbetweenalgorithmsandcircuitlowerbounds |