Теория сложности (старая трешовая версия)
Материал из Викиконспекты
Версия от 11:00, 14 марта 2010;
Fedor
(
обсуждение
|
вклад
)
(
→
Лекция 1
)
(
разн.
)
← Предыдущая
|
Текущая версия
(
разн.
) |
Следующая →
(
разн.
)
Перейти к:
навигация
,
поиск
Содержание
1
Лекция 1
2
Практика 1
3
Лекция 2
4
Лекция 3
5
Практика 3
6
Практика, которой на самом деле не было
7
Лекция 4
Лекция 1
Класс DSPACE
Класс DTIME
Теорема о емкостной иерархии
Практика 1
Сведение по Куку задачи факторизации к языку из NP
Лекция 2
Теорема Кука
Лекция 3
Теорема Ладнера
Теорема Левина
Теорема Бейкера-Гилла-Соловэя
Практика 3
NP-полнота задач о гамильтоновом цикле и пути в графах
NP-полнота задачи о сумме подмножества
NP-полнота задачи о рюкзаке
Практика, которой на самом деле не было
NP-полнота задачи о раскраске графа
Лекция 4
PS-полнота задачи Generalized geography
Навигация
Персональные инструменты
Создать учётную запись
Войти
Пространства имён
Статья
Обсуждение
Варианты
Просмотры
Читать
Просмотр вики-текста
История
Ещё
Поиск
Навигация
Заглавная страница
Свежие правки
Случайная статья
Справка
Инструменты
Ссылки сюда
Связанные правки
Спецстраницы
Постоянная ссылка
Сведения о странице