Теория сложности (старая трешовая версия)
Материал из Викиконспекты
Версия от 13:54, 6 апреля 2010;
192.168.0.2
(
обсуждение
)
(
разн.
)
← Предыдущая
|
Текущая версия
(
разн.
) |
Следующая →
(
разн.
)
Перейти к:
навигация
,
поиск
Лекция 1
Класс DSPACE
Класс DTIME
Теорема о емкостной иерархии
Теорема о временной иерархии
Сведение по Карпу
Сведение по Куку
Класс P
Класс NP
Класс coNP
Практика 1
Сведение по Куку задачи факторизации к языку из NP
Лекция 2
Теорема Кука
Практика 2
Понятие NP-трудной и NP-полной задачи
NP-полнота задачи BH1N
NP-полнота задачи о выполнимости булевой формулы в форме КНФ
NP-полнота задачи о выполнимости булевой формулы в форме 3-КНФ
NP-полнота задачи о клике
NP-полнота задачи о независимом множестве
NP-полнота задачи о вершинном покрытии
Лекция 3
Теорема Ладнера
Теорема Левина
Теорема Бейкера-Гилла-Соловэя
Практика 3
NP-полнота задач о гамильтоновом цикле и пути в графах
NP-полнота задачи о сумме подмножества
NP-полнота задачи о рюкзаке
Практика, которой на самом деле не было
NP-полнота задачи о раскраске графа
Лекция 4
Класс PS
Теорема Сэвича
PS-полнота задачи Generalized geography
Лекция 6
NL-полнота задачи о достижимости в графе
Теорема о связи вопросов EXP=NEXP и P=NP
Теорема Иммермана
Практика 6
Классы Sigma_i и Pi_i
Класс PH
Полиномиальная иерархия
Теоремы о коллапсе полиномиальной иерархии
Практика 7
Класс BPP
Навигация
Персональные инструменты
Создать учётную запись
Войти
Пространства имён
Статья
Обсуждение
Варианты
Просмотры
Читать
Просмотр вики-текста
История
Ещё
Поиск
Навигация
Заглавная страница
Свежие правки
Случайная статья
Справка
Инструменты
Ссылки сюда
Связанные правки
Спецстраницы
Постоянная ссылка
Сведения о странице