Название: Некоторые вопросы сложности алгоритмов
Автор: А.А. Сапоженко
Издательство: М. : МГУ
Год: 2001
ISBN: 5-89407-107-0
Формат: pdf
Страниц: 48
Размер: 11,9 Мб
Язык: Русский

Излагаются результаты по алгоритмическим трудностям синтеза схем и построения минимальных ДНФ, понятия сводимости и NP-полноты, устанавливается связь между временной сложностью вычислений на машинах Тьюринга и сложностью схем.