Open lecture: the problem of the feasibility of Boolean formulas

(Screenshot from presentation: slideplayer.com/slide/3238789 )

We invite everyone to the open lecture of Computer Science Center , dedicated to the problem of the feasibility of Boolean formulas - one of the most famous and important algorithmic problems. The lecture will be held as part of a meeting with students of the online course Algorithms: Theory and Practice. Methods . Time and place: December 25, 19:00, Times Center (St. Petersburg, Kantemirovskaya St. 2A, 4th floor). Participation is free, but registration is required: goo.gl/IiNvV8

The task of feasibility is a canonical difficult task, according to which a huge amount of research is carried out: both practical and theoretical. In particular, this task is devoted to the annual international conference. Every year there are competitions of programs for this task (the so-called Sat-Solvers). Such programs are actively used in many application areas. Just a few months ago, Donald Knuth wrote in Volume 4B of the monograph “The Art of Programming,” a third of which is devoted to the problem of feasibility.
')


The lecture will cover, inter alia, the following questions:
- why the algorithm that solves this problem for polynomial time, put a million dollars;
- as greedy algorithms, iteration with returns, local search, random walks and other techniques are used to develop algorithms for the feasibility problem;
- how exactly sat-solvers are used in practice (we will use sat-solvers to solve some combinatorial problem).