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