Слава разработчикам Лектория!
Слава! Слава!

Иерархия сложностных классов. Полиномиальная иерархия

7-я лекция из курса: Сложность вычислений
1 552 просмотра
15 октября 2014
Теорема о равенстве NL и coNL. Полиномиальная иерархия, внутренние соотношения классов полиномиальной иерархии, их место в иерархии сложностных классов. Пример задачи, принадлежащей полиномиальной иерархии, "схлопывание" полиномиальной иерархии.

Лекторы

кандидат физико-математических наук
Кандидат физико-математических наук. Сотрудник кафедры дискретной математики МФТИ

Следующая лекция

Предыдущая лекция

МАТЕМАТИКА01:17:01
6-я лекция из курса:
Московский физико-технический институт
Московский физико-технический институт (Физтех) – ведущий вуз России по подготовке высококвалифицированных специалистов по передовым направлениям науки и техники. Входит в топ 5 крупных рейтингов отечественных университетов. Отличительной чертой образовательного процесса МФТИ является система поиска и подготовки кадров – знаменитая «система Физтеха».
Скачайте наше мобильное приложение
iTunes
Google Play