Вы здесь

Основы вычислимости и теории сложности. Лекция 6

Лекция
Партнёр:
Предмет:
Дата записи:
24.10.12
Дата публикации:
24.10.12
Код для блога:

Моделирование машин Тьюринга. Недетерминированные машины Тьюринга

Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT.

Страница лекции на сайте Computer Science Center

Другие лекции курса

11