Using Algorithm Configuration Tools to Generate Hard SAT Benchmarks

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10389947" target="_blank" >RIV/00216208:11320/18:10389947 - isvavai.cz</a>

Alternative codes found

RIV/68407700:21230/18:00322875

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Using Algorithm Configuration Tools to Generate Hard SAT Benchmarks

Original language description

Algorithm configuration tools have been successfully used to speed up local search satisfiability (SAT) solvers and other search algorithms by orders of magnitude. In this paper, we show that such tools are also very useful for generating hard SAT formulas with a planted solution, which is useful for benchmarking SAT solving algorithms and also has cryptographic applications. Our experiments with state-of-the-art local search SAT solvers show that by using this approach we can randomly generate satisfiable formulas that are considerably harder than uniform random formulas of the same size from the phase-transition region or formulas generated by state-of-the-art approaches. Additionally, we show how to generate small satisfiable formulas that are hard to solve by CDCL solvers

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA18-07252S" target="_blank" >GA18-07252S: MoRePlan: Modeling and Reformulating Planning Problems</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2018

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the Eleventh International Symposium on Combinatorial Search, SOCS 2018

ISBN

978-1-57735-802-2

ISSN

—

e-ISSN

neuvedeno

Number of pages

5

Pages from-to

133-137

Publisher name

AAAI press

Place of publication

Neuveden

Event location

Stockholm, Sweden

Event date

Jul 14, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—