Radomír Černoch presents 43. PIS - Master-key system design: From NP-completeness to a start-up

On 2019-05-23 16:15:00 at Auditorium S5, MFF UK, Malostranske nam. 25, Prague 1
Master-key system designs also known as the lock-chart problem is a very old
combinatorial problem that emerged in the 19th century but remained almost
unnoticed by theoreticians until the 21st century. The objective is to design
mechanical keys and cylinder locks so that the desired access rights are
respected. The problem is attractive due to its practical motivation, a simple
formalization, a range of practical algorithms and its complexity on the edge
between tractable and intractable. Such properties make it also a perfect
inspiration for student assignments.

In the lecture, I will introduce the lock-chart problem, existing theoretical
results and promising practical algorithms. Among them, the reduction to the
boolean satisfiability problem serves as an excellent opportunity to highlight
the advantages of modern SAT solvers.
Responsible person: Petr Pošík