Основы вычислимости и теории сложности. Лекция 6
ЛекцияПартнёр:
Предмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
24.10.12
Дата публикации:
24.10.12
Код для блога:
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга
Нижняя оценка на палиндром на одноленточной машине Тьюринга. Моделирование k-ленточной машины на k-ленточной с линейным замедлением. Эффективное моделирование k-ленточной машины на 2-ленточной. Недетерминированные машины Тьюринга и класс NP. Задача Circuit-SAT, сведение Circuit-SAT к 3SAT.
Страница лекции на сайте Computer Science Center
Другие лекции курса
11