Laboratory of Mathematical Logic at PDMI

Вторник, 30 июня, Zoom. Начало в 18:30.

Докладчик: Yuri Gurevich (University of Michigan).

Тема: What, if anything, can be done in linear time?

Abstract

The answer to the title question seems to be "Not much." Even sorting n items takes n x log(n) swaps. But, in fact, quite a bit can be done in linear time. We start with an illustration of linear-time techniques. Then we sketch the linear-time decision algorithm for propositional primal infon logic. Finally we mention useful extensions of that logic decidable in deterministic or probabilistic linear time.

Видеозапись:
https://youtu.be/8EuAThXUOXQ

Ссылка на Math-Net.Ru:
http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=27323

Приложение