АиСД S02E15. Сложность задач. Классы сложности.

Алгоритмы и структуры данных. Семестр 2. Лекция 12.
На последней лекции мы поговорили о том, какие задачи решаются за полиномиальное время, какие за неполиномиальное, и какие не решаются совсем. Также обсудили, как одни задачи сводятся к другим, и показали, что задача о рюкзаке является NP-полной
Университет ИТМО, 2022 г.

[@15th_dacha34]

Можно, пожалуйста, пояснить про программу F(x). Ведь если мы напишем её так:
F(x):
if HALT(x,x)
return
else
while true:
pass
Она ведь остановится. В чём проблема?

[@hate_winter]

А куда пропали лекции из плейлиста ?)

[@ambient_cocklushkin]

Павел, а можно на превьюшках писать коротко какие темы в лекции рассматриваются, потому что название видео не всегда видно полностью.

[@pavelmavrin]

Ох это надо все переделывать. Может когда-нибудь займусь

[@likit9403]

Вот насчёт гамильтонова пути, мы же можем перебрать все возможные пути и понять есть он или нет. Такое решение будет за экспоненту, значит задача относиться к EXP классу. Но почему мы её относим к NP классу? Где дистинкция проходит то что мы относим к NP, а не к EXP?

[@pavelmavrin]

Ну класс NP очевидно весь внутри класса EXP, так что противоречия нет

[@likit9403]

@@pavelmavrin Ааа, то есть так она за экспоненту, но можно придумать решение по правилам NP, значит относим в NP. Если решение по правилам NP нельзя придумать то только в EXP заносим, за пределами NP. Спасибо

[@milkrebus3071]

21:32 так chatGPT появился слишком рано

[@whatisagoodusernamehere]

GPT-4 😃