Mann, Zoltán Ádám (2014) Typical-case complexity and the SAT competitions. In: Fifth Pragmatics of SAT workshop.
|
Text
epic1644085565.pdf - Published Version Download (665kB) | Preview |
Official URL: http://easychair.org/publications/?page=629483607
Abstract
The aim of this paper is to gather insight into typical-case complexity of the Boolean Satisfiability (SAT) problem by mining the data from the SAT competitions. Specifically, the statistical properties of the SAT benchmarks and their impact on complexity are investigated, as well as connections between different metrics of complexity. While some of the investigated properties and relationships are “folklore” in the SAT community, this study aims at scientifically showing what is true from the folklore and what is not.
| Item Type: | Conference or Workshop Item (Lecture) |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | Dr. Zoltán Ádám Mann |
| Date Deposited: | 22 Sep 2014 21:34 |
| Last Modified: | 03 Apr 2023 08:16 |
| URI: | http://real.mtak.hu/id/eprint/16019 |
Actions (login required)
 |
Edit Item |
