Search
Complexity seminar
Пятница 15.12. А. Смаль: "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster"
Пятница, 15 декабря, 402. Начало в 12:00.
Докладчик: А. Смаль.
Тема: PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster.
Abstract
Доклад по статье Dominik Scheder, John Steinberger "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster" (http://drops.dagstuhl.de/opus/volltexte/2017/7535/)В докладе будет представлено простое изложение статьи Хертли о PPSZ. Кроме того будет показано, что если мы улучшим PPSZ для Unique-k-SAT, то из этого получится улучшение для обычного k-SAT (но с худшими параметрами).