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

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

Что: Лекция
Когда: Среда, 24 октября 2012, 18:30–19:50
Где: ПОМИ РАН

Описание

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

Видео