Home

Семинар 18 февраля 1999 года

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

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