Классы задач
Описание файла
Документ из архива "Классы задач", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Классы задач"
Текст из документа "Классы задач"
P (и co-P)
Проверка четности
Проверка делимости на 3
Распознавание простоты числа
ЛН (линейные неравенства)
2-ВЫП
ЛП (Метод Эллипсоидов)
NP (и co-NP)
ЗК - Сушествует ли маршрут длины не более B
СЧ - Составные Числа (получается уже P)
NPC (NPC <= NP\P)
ВЫП (выполнимость КНФ)
3-ВЫП
БЛН (булевы линейные неравенства)
ЦЛН
ЗР (Задача о рюкзаке) (распознавание свойств)
P открыта => NP ^ co-NP > P
ЛН принадлежит NP ^ co-NP (что P удалось доказать позже)
NP - трудные
ЗР (Задача о рюкзаке) (оптимизация)
ЗМП (Математическое программирование)
ЦЛП (Целочисленное линейной программирование)
здачи расп. св-в эквивалентные которым есть NPC, а сами они не доказано что NP
задачи оптимизации, для кот. задачи опр. свойств NPC
сводятся по Тьюрингу к NP (т.е. для того к чему сводится есть полиномиальный алгоритм)
все NPC
PSPACE - не более чем полиномиальная память
сильно NPC = полиномиальное сужение есть NPC
БЛН
ЦЛН
замечание: полином сужение задачи ПЧ пусто
не сильно NPC - ЗР
Метод Ньютона:
x_t+1 = x_t - (f''(x_t))^-1 * grad f(x_t)
ЛП:
max <c,x> при Ax<=b
min <y,b> при уA=c, y>=0
Градиентный метод:
z_t+1 = z_t - a_t * grad f(z_t)
наиск. спуск = саму f(z_t+1) -> min
МП: градиентный спуск, потом Ньютон, потом снова градиентный пару шагов