Семинары: Yu. Gurevich, What, if anything, can be done in linear time?

СЕМИНАРЫ


Семинар лаборатории математической логики (Санкт-Петербург) 30 июня 2020 г. 18:30, г. Санкт-Петербург, online

What, if anything, can be done in linear time? Yu. Gurevich University of Michigan
https://youtu.be/8EuAThXUOXQ Аннотация: The answer to the title question seems to be “Not much.” Even sorting $n$ items takes $n \times \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. Язык доклада: английский