Вероятностные вычисления

Вероятностные вычисления. Сложностные классы BPTIME(T(n)), BPP, RTIME(T(n)), RP, coRP, ZPTIME(T(n)), ZPP. Теорема о равенстве BPP{_1/(n^c)} и BPP{_{1/2-1/(2^{n(^d)})}}

Лекторы

Мусатов Даниил Владимирович

кандидат физико-математических наук

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

Конспекты

Комментарий:

Осталось 512 из 512 символов.

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

МАТЕМАТИКА01:08:49

Вероятностные алгоритмы. Теорема Гача-Сипсера

12-я лекция из курса:

Сложность вычислений

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

МАТЕМАТИКА01:09:05

Теорема Мейера. Языковые классы NC^d, AC^d. P-полнота

10-я лекция из курса:

Сложность вычислений