(2021.12.08) 알고리즘 수업 들으면서 정리하기 25탄 w15-1 실강 정리 halting problem 을 배웠다. NP 정의도 배웠다. 교수님이 이 부분을 굉장히 자세하게 천천히 많이 설명해주셔서 오늘도 진도를 많이 안나갔다 교수님 추천 영상 https://www.youtube.com/watch?v=92WHN-pAFCs&feature=youtu.be Halting Problem (unsolvable problem) 프로그램 P와 input i 가 있고, 프로그램 P에 input i 를 넣는다. 그러면 두가지의 상황이 발생한다. > P halts on i > P runs forever on i 프로그램 P와 input i 가 있을 때, P가 i에 halt인지 아닌지를 알아낼 수 있는 프로그램 H..