Phase transitions and thresholds, the Advanced Encryption Standard (AES), databases for combinatorial problems, and heuristics for SAT solvers (III)

Oliver Kullmann

(Swansea University)

Random propositional formulas (CNF's) and their satisfiability distribution have attracted a great deal of attention in the area of complexity theory and algorithms, especially since the connection with the nature of phase transitions in Physics is under investigation (see "Determining computational complexity from characteristic 'phase transitions'"in Nature, 1999, volume 400, pages 133-137).

Based on AES (the successor of DES) I want to present a new generator ("OKsolver") for random CNF's and discuss, why this generator is useful. A large database for these instances shall be built up to systematically explore the phenomenon of phase transitions (experimentally and numerically). Finally I will present a program how to use this database in order to get a general adaptive heuristics for a given SAT solvers A, resulting in a (hopefully) improved SAT solver A'.
Thursday 21st March 2002, 14:00
Robert Recorde Room
Department of Computer Science