Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 1. Машины Тьюринга и булевы схемы
Теория сложности вычислений

Что: Лекция
Когда: Вторник, 14 сентября 2021, 18:30–19:50
Где: Конференция в zoom, Онлайн
Слайды: computationalcomplexity_lecture_140921.pdf

Описание

Машины Тьюринга. Сложность распознавания бинарного палиндрома на одноленточной машине Тьюринга. Булевы схемы. Распознование языков булевыми схемами. Классы DTime, P, Size, P/poly.

Видео