Open Collections

Random k-sat. A review and some new results.

Banff International Research Station for Mathematical Innovation and Discovery

In this talk I will both give a review of the behaviour of random k-sat formulae and present some new variations on the problem. In the study of random K-sat one constructs a k-sat formula with n variables and m clauses at random. When m is small the formula is most often satisfiable and when m i large it is most likely unsatisfiable. We also know that there is a sharp transition between these to cases, often referred to as a phase transition. Empirically is has been observed that sat-solvers have a peak in their typically running time when m is close to this phase transition, and a longer number of conjectures has been made about this behaviour.

I will review what is now known from mathematical results and also discuss how well, or badly, some of the old conjectures and observations have held up against both mathematics and recent, far more extensive, experiments. I will also mention some recent work on unbalanced versions of k-sat which display interesting behaviours.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: Umeå universitet

2019-04-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/69473

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/