A continuous-time Max-SAT solver with high analog performance

Datum

21.06.2019

Zeit

11:00 - 12:00

Sprecher

Dr. Maria Ercsey-Ravasz

Zugehörigkeit

Babes-Bolyai University, Romania

Sprache

en

Hauptthema

Biologie

Host

Carl Modes

Beschreibung

Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class of problems where the task is finding Boolean assignments to variables satisfying the maximum number of logical constraints. Since MaxSAT is NP-hard, no algorithm is known to efficiently solve these problems. Here we present a continuous-time analog solver for MaxSAT and show that the scaling of the escape rate, an invariant of the solver’s dynamics, can predict the maximum number of satisfiable constraints, often well before finding the optimal assignment. Simulating the solver, we illustrate its performance on MaxSAT competition problems, then apply it to two-color Ramsey number R(m, m) problems. Although it finds colorings without monochromatic 5-cliques of complete graphs on N ≤ 42 vertices, the best coloring for N = 43 has two monochromatic 5-cliques, supporting the conjecture that R (5, 5) = 43. This approach shows the potential of continuous-time analog dynamical systems as algorithms for discrete optimization. As another interesting example we present a Sudoku solver based on this algorithm and show how it helps us define a type of "Richter scale" to characterize the hardness of Sudoku problems.

Letztmalig verändert: 22.06.2019, 00:08:31