REAL

Typical-case complexity and the SAT competitions

Mann, Zoltán Ádám (2014) Typical-case complexity and the SAT competitions. In: Fifth Pragmatics of SAT workshop.

[img]
Preview
Text
epic1644085565.pdf - Published Version

Download (665kB) | Preview

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 Edit Item