×

Satisfiability and computing van der Waerden numbers. (English) Zbl 1204.05097

Giunchiglia, Enrico (ed.) et al., Theory and applications of satisfiability testing. 6th international conference, SAT 2003, Santa Margherita Ligure, Italy, May 5–8, 2003. Selected revised papers. Berlin: Springer (ISBN 3-540-20851-8/pbk). Lect. Notes Comput. Sci. 2919, 1-13 (2004).
Summary: In this paper we bring together the areas of combinatorics and propositional satisfiability. Many combinatorial theorems establish, often constructively, the existence of positive integer functions, without actually providing their closed algebraic form or tight lower and upper bounds. The area of Ramsey theory is especially rich in such results. Using the problem of computing van der Waerden numbers as an example, we show that these problems can be represented by parameterized propositional theories in such a way that decisions concerning their satisfiability determine the numbers (function) in question. We show that by using general-purpose complete and local-search techniques for testing propositional satisfiability, this approach becomes effective – competitive with specialized approaches. By following it, we were able to obtain several new results pertaining to the problem of computing van der Waerden numbers. We also note that due to their properties, especially their structural simplicity and computational hardness, propositional theories that arise in this research can be of use in development, testing and benchmarking of SAT solvers.
For the entire collection see [Zbl 1030.00034].

MSC:

05D10 Ramsey theory
03B35 Mechanization of proofs and logical operations
68Q25 Analysis of algorithms and problem complexity
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)

Software:

BerkMin; SATO; Chaff
PDFBibTeX XMLCite
Full Text: DOI