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

[@hate_winter]

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

[@15th_dacha]

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

[@likit9403]

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

[@pavelmavrin]

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

[@likit9403]

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

[@milkrebus3071]

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

[@whatisagoodusernamehere]

GPT-4 😃