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

Лекция 1. Машины Тьюринга и булевы схемы
Computational Complexity Theory

What: Lecture
When: Tuesday, 14 September 2021, 18:30–19:50
Where: Конференция в zoom, Онлайн
Slides: computationalcomplexity_lecture_140921.pdf

Description

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

Video