×

zbMATH — the first resource for mathematics

Green-Tao numbers and SAT. (English) Zbl 1259.68182
Strichman, Ofer (ed.) et al., Theory and applications of satisfiability testing – SAT 2010. 13th international conference, SAT 2010, Edinburgh, UK, July 11–14, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14185-0/pbk). Lecture Notes in Computer Science 6175, 352-362 (2010).
Summary: We aim at using the problems from exact Ramsey theory, concerned with computing Ramsey-type numbers, as a rich source of test problems for SAT solving, targeting especially hard problems. Particularly we consider the links between Ramsey theory in the integers, based on van der Waerden’s theorem, and (boolean, CNF) SAT solving. Based on Green-Tao’s theorem (“the primes contain arbitrarily long arithmetic progressions”) we introduce the Green-Tao numbers \(\text{grt}_{m }(k_1, \dots, k_m)\), which in a sense combine the strict structure of van der Waerden problems with the quasi-randomness of the distribution of prime numbers. In general the problem sizes become quickly infeasible here, but we show that for transversal extensions these numbers only grow linearly, thus having a method at hand to produce more problem instances of feasible sizes. Using standard SAT solvers (look-ahead, conflict-driven, and local search) we determine the basic Green-Tao numbers. It turns out that already for this single case of a Ramsey-type problem, when considering the best-performing solvers a wide variety of solver types is covered. This is different to van der Waerden problems, where apparently only simple look-ahead solvers succeed (regarding complete methods). For \(m > 2\) the problems are non-boolean, and we introduce the generic translation scheme for translating non-boolean clause-sets to boolean clause-set. This general method offers an infinite variety of translations (“encodings”) and covers the known methods. In most cases the special instance called nested translation proved to be far superior over its competitors (including the direct translation).
For the entire collection see [Zbl 1196.68013].

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
05D10 Ramsey theory
11B25 Arithmetic progressions
Software:
UBCSAT
PDF BibTeX XML Cite
Full Text: DOI