City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Недетерминированные и вероятностные вычисления: обзор
Non-deterministic and probabilistic computations

What: Lecture
When: Monday, 04 April 2016, 17:00–18:20
Where: 2-й учебный корпус К(П)ФУ, ауд. 907

Description

Что такое недетерминированные и вероятностные вычисления: различные подходы. Класс NP и примеры задач из него. Определения вероятностных классов и простейшие соотношения. Другие недетерминированные сложностные классы и соотношения между ними. Обзор известных результатов о проблемах равенства классов.