Laboratory of Mathematical Logic

Четверг, 18 февраля, комната 106. Начало в 18:00.

18 февраля.
Б.Конев. Оракульные вычисления (источник -- книга Ch.Papadimitriou "Computational Complexity", раздел 14.3).
Abstract
Доклад будет посвящен оракульным вычислениям и возможности их применением к задаче установления равенства/неравентсва сложностных классов. Будет, в частности, показано, что существуют оракулы A и B, для которых 1)

, 2)

. Тем самым, будет показано, что знание уравнивающего или разделяющего оракула, вообще говоря, ничего не добавляет к знанию о равенстве/неравенстве сложностных классов.