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

Моделирование машин Тьюринга. Недетерминированные машины Тьюринга
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 24 October 2012, 18:30–19:50
Where: ПОМИ РАН

Description

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

Video