알고리즘 - NP

다음주 화요일 6월 9일 시험을 볼텐데 지난 중앙무사때와 마찬가지로 강의실 말고 다른 강의실을 정해가지고 시험을 그 장소에서 볼테니까 시험 보기 전에 공지상에 올라온 시험 장소 확인하고

지금을 보러 보시면 될 것 같아요. 아마 작년이나 지난 중간고사 때와 아마 같은 강의실이 될 가능성이 많긴 한데 그게 좀 아직 확실하지는 않아서 아무튼 여러분들이 확인을 하고 기말고사 강의실로, 고사실로 다음 주 화요일 날 보기를 바래요. 자 이제 범위는 오늘 하고 이제 다음 동영상 강의까지 할 구장까지가 범위가 될 거고 중간고사 이후부터 제품을 팀장에

다 하지 못한 부분부터 살펴보도록 하죠.

실전에서는 이 솔딩이라는 문제에 북한해서 어떠한 종류의 알고리즘이 만들어지던 간에 그 알고리즘이 가지는 어떤 특성이 있다고 했을 때 그런 특성을 갖는 알고리즘은 어떤 효율성에 측면에서 이러한 한계를 갖는다 라는 것을 얘기하려고 하는 챕터 중에서 어떤 문제를 중심으로 그것을 푸는 알고리즘에 대한 효율성 측면에서의 한계, 바운드 그것을

따져보려고 하는 건데 그래서 앞에 힙솔트 같은 것들도 기본적으로는 어떤 트리 구조를 이용 힙이라는 구조를 이용해서 솔팅을 하는데 그것도 바운드가 엔 로그인이다 라는 것 살펴봤었어요. 자 그러면은 우리가 여태까지 살펴본 솔팅 알고리즘 여러가지 알고리즘 설계 유형에 따라서 많이 만들어 봤었는데 퀵솔트니 또 뭘 지수 올 테니 또 방금 요 앞에서 살펴본 힙솔트니

다 보면 worst case and time complexed가 end of well 이었죠. 그래서 여태까지 많은 알고리즘을 볼 때 그것보다 낮아지는 그런 알고리즘이 없는 것으로 실제 이제 얘들이 이렇게 보이는데 이게 정말 그 sorting을 하는 알고리즘이 가지는 효율성에 있어서의 한계인지

대해서 이 시간에 살펴보려고 해요. n로그 n보다 더 낮아질 수는 없는 건가? 그래서 그거에 대한 답을 해보려고 하는데 일단 어떤 쇼팅 문제에 국한해서 쇼팅 알고리즘을 우리가 만들어놨다고 생각을 하고 그 쇼팅 알고리즘이 지금 어떤 비교를 통해서 킥값의 비교를 통해서 솔팅하는 알고리즘이라면

우리가 여태까지 살펴본 그런 경우들을 대부분 이랬죠. 어떤 array에 위치해 있는 키 값들끼리 값을 비교를 해서 순서만 안 맞으면 순서를 바꾸는 형태로 이렇게 sorting을 했어요. 그래서 그런 방식으로 sorting을 하는 알고리즘의 경우 가지는 한계 lower bound에 대해서 따져보려고 해요. 내려온 order가 낮춰질 수 있을 때 얼마만큼까지 낮춰질 수 있을지 lower bound에 대해서 그 이 살펴본 건 앤 로그인인데 그게 정말 로라운인지 보려고 해요.

그래서 예를 들어서 지금 어떤 sorting 알고리즘인데 3개의 키 값을 가지고 sorting을 하는 알고리즘을 하나 우리가 생각을 해보죠. 그래서 sort 3 세 개의 element를 sort 한다. 그래서 s라는 array에 숫자가 3개가 있었던 키 값이. 그래서 편의상 서로 다른 키가 있다라고 해보죠. s1, 2, 3 이렇게 각각의 값들을 a, b, c라고 우리가 생각을 해보죠. s1에 있는 값이 a, s2에 있는 값이 b, s3가 비슷합니다.

그러면 이제 맨 처음에 이렇게 값이 들어있는 걸 꺼요. B가 맨 앞에 B가 그 다음에 C가. 자 그러면은 이 A가 각각 어떤 값을 같은 값을 가질 텐데 이거를 SORT하는 알고리즘으로서 어떤 식으로 만들어려고 하냐면은 일단 이 A, B, C 각각의 값을 비교하는 일들을 할 텐데 일단 먼저 이 두 개를 비교해서 어떤 일을 하고 만약에 이 조건이 아니면은 이제 B, C를 또 비교하고 그래서 그렇다면은 이거 하고 그렇지 않으면은 뭐예요? 이것도 아니고 이것도 아닌 조건이라면 서로 다르다고 했을 때

A, B, C의 순서가 반대로 되어 있는 그런 변화는 보고 그러면 결국 솔로팅을 했을 때는 C, B, A 값이 SA 이렇게 1, 2, 3, 번, X에 오도록 해주시면 되는 거겠죠. 그래서 최종적으로 솔로팅이 됐을 때 C, B, A 순서로 솔로팅이 돼야 된다. 이거는 뭐 더 이상의 이 비교 두 번 하고 나서 더 이상의 다른 비교를 하지 않더라도 얻을 수 있는 결론일 테니까 이 순서로 Y, A에 넣어주면 그 조건을 만족하는 팀들에 대해서는 소통이 된 걸 거예요.

이 조건이 만족되었을 때 어떤 비교를 할 건지 더 할 건지 그것도 마찬가지 비교를 더 할 건지 정해주면은 이제 소울트가 제대로 될 수 있을 텐데 이 경우 a는 b보다 작다라는 조건일 때는 그러면 b하고 c를 비교를 해서 b가 만약에 c보다도 작다 지금 a는 b보다 작다는 조건이 만족됐는데 거기에 들어가서 b하고 c를 비교했더니 b는 c보다 작다라면 어때요? A하고 B하고 C 사이에 순서대로 되어 있는 거죠

B가 제일 작고 B가 그 다음이고 C가 그 다음이고 그러니까 그 순서 그대로 놔두면은 SORT가 되는 상태가 되는 거고 만약에 이게 아니라면은 C는 B보다 SORT가 작다라면은 B가 크다 그 다음에는 A하고 B 사이의 관계는 지금 이런 상태인데 B, C 해봤더니 둘 사이에는 또 C가 B보다 작은 거더라 그러면 A하고 C가

어떤 관계가 되는지를 비교를 해서 그거에 따라서 A, B, C의 순서를 이렇게 정해주면 될 거에요. 그렇죠? 그래서 뭐 이런 경우라면 이 순서가 될 거고 그렇지 않다면 이 순서가 될 거고. 그렇겠죠? 그 다음에 이게 이 점점점점으로 된 부분을 제대로 만들어 준 걸 테고 이 부분도 마찬가지로 이것도 아니고 이것도 아닌 경우 아, 이거인 경우, 이거는 아닌데 이거인 경우에 그러면 또 A하고 C를 비교를 해서

만약에 그렇다면 B, A, C, 그렇지 않다면 또 다른 순서 B, C, A, 이렇게 순서를 3개에 대해서 정해주면 되겠죠. 그러면 3가지가 있을 수 있는 모든 경우에 대해서 다 따져서 순서를 정해준, 즉 3개에 대해서 제대로 하는 결골이등으로 만들어지면 되겠죠. 그랬을 때 여기 비교 연산들을 이렇게 하면서 어떤 결론을 메이든지 또 비교를 더하든지 이렇게 진행을 하는데 그 비교 연산들을

진행되는 순서대로 이렇게 생각을 해보면 매첨 A는 B보다 작은가? 요거, 그렇죠? 매첨의 비교를 하죠. 그래서 만약에 그렇다라면 이 점점점에 해당하는 것을 들어가서 이제 또 이 비교를 하죠. 그렇죠? 그래서 만약에 그렇다라면 어때요? 그때는 더 이상의 비교 없이 순서는 A, B, C가 돼야 되는구나. 그렇죠? 이 순서를 결정할 수 있어요. 그렇죠? 그렇죠? 그 다음에 이게 아니라면은, 이게 아니라면은 이제 요 비교를 또 한 번 하죠. 그렇죠? 아닌 경우에는 비교를 또 해요.

그래서 그때는 이제 요구 비교 결과에 따라서 순서를 정할 수가 있죠. 그래서 이게 그렇다 라면 요구 보건 아니다라면은 CAP이고 그렇죠 이렇게 되는 거죠. 그래서 요것이 만족된 경우에는 요렇게 접수들이 만들어질 거고 요것이 아니었다 여기서부터 아니었다 라면은 여기서 또 시작을 할 테니까 똑같은 방식으로 뭐 어떤 게 형에 죽고 였으면은 동물 같고 이런식으로 쭉

이렇게 만들 수가 있죠. 그래서 그러한 형태의 실행이 되면서 루트부터 비교연산, 어떤 연산이 행해지는지 그 연산의 결과가 무엇인지의 이 부분이니까 결과에 따라서 이렇게 다음번에 해야 될 일이 뭔지를 쭉 서브트리로 만들어 나가는 그런 위태로 만들어 놓은 것 그리고 최종적으로 이 리프 부분에 어떤 결정에 해당하는 것

순서에 결정되게 되면은 소리로 하는거니까 abc 구성서대로 123 인덱스에 들어가야 된다 그 다음에 a c b 순서로 123 인덱스에 들어가야 된다 이렇게 이런 최종적인 소리로 엘리먼트들의 배연에 들어가야 될 순서를 결정해주는 것을 리프로 담고 있는 이러한 구조를 디시전 트리로 불러요 조건을 인터넷 트리터는 여기 뭐 그린색으로 하늘색으로 이렇게 표시가 되어 있는

internal node에는 그런 조건을 확인하는 부분이 있고 리프 노드에는 그 조건에 따른 어떤 조건에 만족되느냐 아니냐에 따른 결정값을 갖고 있는 리프 노드의 그런 트리를 decision tree, 결정 tree라고 부르는데 이 soft tree라고 하는 알고리즘의 결정 tree가 이런 식으로 만들어질 수 있겠다는 거죠 그러면 그 결정 트리를 보면 이게 지금 abc가 있을 수 있는 순서대로 있을 수 있는 모든 경우들이 네 여섯 가지 경우, 그렇죠?

IBC 대 펄루테이션의 수조 근데 어떤 사례에 대해서는 어떤 순서 입력 값에 대해서는 비교를 두 번 하고 그 순서를 결정할 수 있고 어떤 경우들에 대해서는 한 번, 두 번, 세 번 어떤 거나 다 세 번씩 이렇게 비교를 하고 순서를 결정하고 또 어떤 거는 두 번 하고 이런 식이죠 그렇죠? 그래서 이 알고리즘은

6가지 모든 ABC가 있을 수 있는 순서를 다 생각했을 때 제일 많이 비교를 하는 게 3번이에요 비교 연설을 3번 수행하면 프로트가 완료가 되는 그런 알고리즘이죠 어떤 경우에는 2번만 해도 결정을 할 수 있는 경우였고 그래서 이거는 실제 각 크기 비교 결과에 따라서 불필요한 추가의 비교

원래 비교했던 거를 또 한 번 하는 순서가 지금 계속 바뀌어지고 하다 보니까 일반적인 알고리즘의 경우에는 원래 했던 그 두 개의 원소들끼리 비교를 했던 거를 다음에 또 하게 되는 그런 알고리즘들이 있는데 이거는 그런 불필요한 비교, 이미 한 번 했던 비교는 다시 행하지는 않는 거죠. 그래서 비교의 숫자를 모든 동물에 최소화할 수 있는 그런 알고리즘으로서 만들어진

라는 것을 지금 할 수 있어요. 세 개를 트롯트 하는데 예를 들어서 두 번의 비교가 최소한 필요하고 한 번만 비교해서 세 개의 순서를 정할 수 있는 방법은 없어요. 최소 두 개 하고 또 어떤 경우는 세 번 하고 아무튼 그 과자에서 불필요한 그런 비교를 더 하지는 않는 방식이다. 라는 것을 디시션 출입봉할 수 있는데 자 그러면 우리가 알고 있는 또 다른 알고리즘 예를 들어서 익스젠지 소울트 이런 생각을 해보죠.

그것도 세 개만 정수 로트를 하는 예로서 decision tree를 한번 만들어 보죠 exchange sort 어떤 방식으로 하는지 잘 알 테니까 맨 처음에 이렇게 있을 때 decision tree 만들어 보면은 이 코드대로 쭉 수행을 해서 i, j 비교하는 거를 그대로 i, j 따라가면서 어떻게 하는 거를 보면은 거기 처음에 index에 들어가 있던 값을 abc라고 했을 때 맨 처음에 b하고 a 비교, 이 비교를 하고 그 다음에 그런 경우 실제 현재

익스체인지를 하죠. 그렇다면 큰 것이 작은 것에 비해서 앞에 와 있는 경우라면 그걸 진짜 바꾸는 일을 하죠. 익스체인지를 해요. 그리고 거기에 대해서 또 바꿔진 것 가지고 이 인덱스에 따라서 결과적으로 비교되는 게 C하고 B에 비교인데 이렇게 순서로 따지면 이 방향으로 따지면 이거를 비교를 해요.

그래서 예수하면은 실제 작은 것이 지금 뒤에 와 있으니까 또 순서를 바꾸고 그래서 결과적으로 이렇게 만들어 놓은 상태에서 그거를 계속 진행하는 것을 따라가다 보면은 예수인 경우 실제 B가 A보다 작고 C가 B보다 작고 B가 C보다 크고 그러니까 뭐예요? 실제 사실은 이 두 개만 보면은

A가 제일 크고 그 다음에 B고 그 다음에 C다. 즉 작은 순조로 하면 C가 A가 더 커야 될 거고 그 다음에 B 그 다음에 A. 그렇죠? 이렇게 돼야 되겠다는 건데 이거는 실제 이 연산을 또 한 번 해요. 코드 상에서 그대로 따라가다 보면은 밖에 위치에 있는 것 가지고 하다 보면은 이 연산은 또 해요. 즉 앞에 비교해서는 이미 했는데 이 알고리즘 그대로 주행을 하다 보면은

이거 비교가 또 한 번 수익이 되는 거예요. 위치가 바뀜으로 해서. 그렇죠? 그러면 이거에 대해서는 매일 처음에 비교했을 때는 그럴 수도 있고 아닐 수도 있겠다지만 지금 이미 그런 상태로 왔으니까 이 경우에 답은 예수 밖에 없죠. 그렇죠? 예수인 경우는 이 순서대로 A가 제일 크고 그 다음에 B고 C 그래서 이 순서대로 이렇게 하고 이제 끝낼 거예요. 그렇죠? 저존소. 그리고 이 경우에는 비교가 NO가 나올 수 없는 비교예요.

왜냐하면 이 길을 따라온 것이기 때문에 예스인 경우도 따라왔는데 밑에 와서는 A하고 B가 값이 바뀌지는 않을 테니까 위치만 바뀌었지 크기가 바뀌지는 않으니까 NO가 나올 수 없죠 그래서 이 경우에는 NO 브랜치를 가지질 않아요 그렇죠? 그러면 이거는 지금 예스 브랜치에 따라서 이렇게 오고 여기는 NO 브랜치가 없었는지 한 번 내려봐라 이 경우라면 또 경우도 있을 수 있죠

그러면은 이런 상태라는 거고 그때는 바뀐 것들 가지고 C 하고 A를 이렇게 이 방향으로 비교해요. 그러면 이 경우는 예수는 다 나올 수 있죠. 예수인 경우 세 개의 관계를 가지고 따져보면 B, C 순서로 되어야 된다는 거고 노인 경우는 이런 순서로 B, C 순서로 되어야 된다는 거고. 그 다음에 이 경우 매첨에 따졌을 때는 노, 예수는 있을 수 있고 당연히 노도 있을 수 있겠죠.

그래서 no인 경우라면은 이제 또 가지고 비교를 해보면은 c하고 a를 이 방향으로 비교를 하고 이 경우 yes이면 b가 a보다 작다가 아니다. 그 다음에 c가 a보다 작다인 경우는 이제 비교를 또 이렇게 코드상으로 보면 A 하고 B, 여방행으로 비교를 해야 됩니다. 그래서 이 경우는

이거 A하고 B의 비교인데 이거랑 방향은 바꿔서 비교를 하는 거지만 이미 결과는 여기서 정해지는 거죠 그래서 마찬가지로 값이 이게 no였으면 여기 yes일 수밖에 없고 no인 경우는 안 나오죠 이렇게 반대로 바뀌었으니까 그렇죠? 그래서 여긴 오른쪽 좌우도 없는 형태예요 그다음에 이 경우는 no인 경우 비교하고 그렇죠? 그러면 이 경우는 각각 이렇게 다른 경우가 예수들 모두 다 나눠줄 수 있고

이렇게 나와요. 6가지 방법으로서. 그러면 이 툴이 만들어진 것을 보면 모든 순서 결정을 하는 데까지 다 3번씩. 모든 경우에 다 어떤 경우든 3번씩 다 비교를 해요. 그러면 실제 이 Exchange Sort Alboridhme 이것에 비해서 모든 경우에 다 3번씩 하는 거니까 지금은 실제

모든 사례에 대해서 따져보면 더 많게 하겠죠. Trot-3의 방식에 비해서. 이건 어떤 경우는 두 번만 하고 두 번 내는데 이거는 모든 경우에 다 생겨야 되는 거니까. 자, 그래서 이렇게 Dishon Tree로 만들어 보면 실제의 알고리즘이 수행을 하는 그 기종두의 경과를 낼 때까지 각각의 Permutation에 대해서 몇 번을 해야 되는지 나오죠. 그러면 worst case behavior 따진다면

최악의 경우 비교 횟수 이걸 이게 될텐데 알고리즘이 input n에 대해서 실제로 수행해야 되는 최악의 비교 횟수 근데 여기 3인 경우에 ExchangeSort는 비교를 최악의 3번이고 이것도 최악의 경우는 3번이에요 그렇죠? 근데 이거는 어떤 왼쪽에 있는 이 솔루스3이라는 방식은 어떤 input에 대해서는 뭐라도 비료를 두 번 하고 프로팅이 끝나는

이런 알고리즘이죠. 그래서 최악의 비교 따졌을 때 이거는 뭐 세 번이긴 한데 최상으로 따지면 비교가 조금 더 적을 수 있는 물론 포견적으로 따져도 이쪽 방식이 이쪽에 비해서 좀 더 적은 비교를 비교를 하는 겁니다. 라는 것을 알 수가 있죠. 자 그래서 이제 이러한 decision tree를 이용해서 최악의 경우라는 것은 이거 뭐예요? 결국은 비교 횟수라고 하는 것은 이 깊이

decision tree 에서의 깊이예요. 그쵸? tree의 깊이예요. 제일 depth가 깊은 leaf node의 깊이예요. tree의 깊이예요. 이게 최악의 경우에 비교했었죠. 그죠? 알고리즘이 있을 때 가진 않습니다. 지금 여기가 xn-sort는 n이 3인 경우에 비교 없이 최악의 경우 3번씩 다 하는 거였고 그래서 요거는 일반화해서 n인 경우에 어떤 알고리즘의 decision tree를 만든다면 그쵸?

그 제일 깊은 깊이 그것이 실제 그 알고리즘의 최악의 비교할 수가 되겠죠 그쵸? 그거를 지금 우리가 3이라는 3일 때 예를 가지고 살펴봤는데 일반화해서 N일 때 몇 분으로 나오는지 만들어 보려고 해요 그쵸? 그럼 이제 이런 비교를 한다면 이 트리는 기본적으로 뭐예요? 트리 중에서? binary 트리죠.

유옥가 수냐 볼수냐 예스냐 뭐냐 꼭 한만에 좀 더욱더에 걸어서 나오는 거니까 예스 노 주어 볼 수 있죠. 바이너리 트레이 하나의 노트가 다음 번에 두 개의 차이드를 가질 수 있는 최대 2개 정도. 이런 식으로 없는 경우도 있고 이건 하나만 있는 경우도 있고 최대 2개 정도. 바이너리 트레이죠. 바이너리 트리가 N개의 키들을

폴트를 한다고 했을 때 binary tree로 만들어지는 decision tree의 최대의 깊이 그거를 따지면 최악의 비교수, worst case complexity가 나온다 라는 거죠. 어떤 알고리즘에 대해서 자 그러면은 그러면은 지금 여기 세 개면은 전체 바깥에 이렇게 리프에 노란색을 가진 것들이 몇 개가 있어요

저 세 개가 순서를 가질 수 있는 프로젝트 순위니까 N이면 디시전 트리 만들어 놓으면 N개에 대해서는 디시전 트리가 N 팩토리얼게 리프를 가지게 했죠 그렇죠? N 팩토리얼게 여러 개 노란 색깔 칠해진 단말 노드가 N 팩토리얼게만큼 했어요 N 일반적인 N 값에 대해서 가지면 자 그러면 N 팩토리얼게의 리프를 가지는

그렇죠? binary tree에 최대의 깊이가 얼마일까? 골을 어떤 수식으로 계산을 해낼 수 있으면은 그게 바로 비교에 의해서 솔딩을 하는 알고리즘, 키값의 비교를 통해서 솔딩하는 알고리즘에 최악의 제일 많은 비교의 수가 나와요. 그렇죠? 루트루트까지 도달할 때, 요거를 제외한 비교 1, 2, 3 요까지 도달하는 첫 데프트죠.

자 그래서 이제 그거를 일반화해서 n 에 대해서 어떤 식으로 나오는지 괜히 3일 때는 예를 들어서 이런 알고리트문 3 그것도 3 뭐 이런걸 알 수 있는데 일반화 일반적인 n각에 대해서 어떻게 나오는지 이제 수학적으로 그 사실은 이제 보려고 하는데 그래서 여기 이제 여러가지 정리들에 형태로서 이런 정리 이런 정리 이런 정리 또 이런 레몬. 그리고 또 롬고.

이것들을 통합해서 결론 지으면 제일 깊은 깊이가 얼마다 이런 식으로 나온다 이것보다 더 깊어지는지는 않는다 이것을 로우 바운드로서 보이는 거예요 더 짧아지진 않는다겠죠 바운드로서 가진다면 자 그래서 일단 정리 또는 레머 천테럼 또는 레머 몇 가지 쭉 그냥 실제로 다 증명이 필요한 것들이지만 수학적인 증명은 우리가 지금

굳이 할 필요는 없을 것 같고 일단은 직관적으로 아 그렇겠구나 라는 것을 알 수 있을 정도의 렘어학 대우립 드럼으로 이렇게 만들었어요 그래서 일단 렘어학 별 첫 번째 렘으로서 모든 디터미니스틱 알고리즘 여태까지 우리가 지금 만들어 본 모든 알고리즘이 다 디터미니스틱 한 건데 요건 디터미니스틱의 개념 단 디터미니스틱의 개념 요건은 좀 있다가 구정해서 다시 볼텐데 아무튼 여태까지 우리가 살펴본 모든

알고리즘은 다 Deterministic 한 거였어요. 그런 알고리즘인데 N개의 서로 다른 Key를 Sorting하는 그런 알고리즘의 경우 각각의 알고리즘이 그거에 해당하는 Decision Tree를 가질 수 있다고 했죠. 그래서 Decision Tree로 아까 얘기했듯이 N개의 면은 N Factorial Galee프를 갖는 Decision Tree로 만들어질 수 있다고 했어요. 그렇죠?

모든 NTA의 순서에 대해서 다 할 수 있어야 되는 거니까 그렇죠? 그래서 이거 당연히 그렇겠죠. 그래서 뭐 "Froomed Bailerid Binary Decision" 추리 라고 해놨는데 뭐 "Froomed" 됐다는 걸 이런 식으로 실제 더 이런 것처럼 불필요한 연산을 더 하지 않는 식으로 이렇게 가지가 쳐진 가지치기를 한 그런 방식의 줄이다라는 거예요. 아무튼

이런 트리가 존재한다. 첫번째 우리가 받아들이는 lemer이고, 두번째 lemer, worst case comparison, 최악의 비교 횟수, 이렇게 만들어진 이 트리의 depth이다. 그리고, 이 트리의 깊이다. 제일 depth가 깊은 리브노드의 깊이다.

그쪽 트리의 깊이가 있죠. 그것도 주반적으로 그렇다라고 좀 얘기할 수 있는 거고요. 그 다음에 이제 M개의 어떤 binary 트리에 리프가 M개가 있다. M 이라고 했을 때 그리고 그 binary 트리의 깊이가 D다 라고 했을 때 이 M하고 D 사이의 관계는 어떻게 되는지를 보여주는 레머가

7.3 에요 그래서 m 이 바이너의 주위에 있는 전체를 이후에 쓰고 d 가 대표다 그러면은 요기 값이 요 로그의 저 베이스 투로 하는 로그 m 에 세례는 장 그가 보다 그거라 같다 요것도 수학적으로 증명할 수 있어요 그래서 다 그 증명하지는 않을 텐데 어떤 d 하고 m 사이에 관계 뭐였죠 그 깊이 하고 그 이후에 수 하고의 관계

이 D값이 이것보다 크거나 같아요. 그러면 일반적인 M, B 리프의 수라고 했는데 아까 우리가 얘기한 N값을 초보하는 때 나타나는 Decision Tree의 리프로드의 수는 뭐였어요? N-VACTORIAL 이랬죠. M 대신 N-VACTORIAL을 우리가 생각하는 D-VACTORIAL

이 시전 트리에 대입해보면 이렇게 되겠죠. 여기 있는 이 값이. 그렇죠? M 팩트럴리어를 가지면 최악의 경우 최소한 이만큼의 비교 제일 깊은 데에서부터 이만큼의 비교는 해야 되는 거니까 이만큼의 비교를 필요로 할까요. 그렇죠? 여기 M 대신에 M 팩트럴리어를 쓴 거예요. 깊이가 이거보다는 크거나 같다고 했으니까 이만큼의 비교는 비교하다는 거죠. 깊이까지 갈 때 비교할 수 낮으면

자 그럼 이제 거의 다 왔어요. 이게 최악의 경우에 비교 횟수에 로우 바운드에요. 이만큼은 최선이 필요하다. 이것보다 더 작게 해서는 안된다라는 거죠. 그래서 n 팩토리얼이라는 것은 n 곱하기 n-1 곱하기 n-2 해가지고 쭉 곱해진 거니까 여기까지. 그러면 로그를 찍은 걸 생각하면 로그 n+ 로그 n-1+ 로그 n-2.. 로그 2 로그 1까지 더한 거 합시다.

곱한거에 로그 씌우면 로그가 다 더한 값으로 될테니까 그래서 그 값을 n, n-1 로그 씌운 그 값들을 생각해서 정리를 하면 우리가 앞에 그전 값 계산할 때도 이런 비슷한 것들이 나왔는데 그 값이 n 로그의 -1.45n 이라는 값하고 거의 유사한 값으로 되요.

앤팩토리얼은 없이, 그래서 요게 실제인, 실제 요거보다는 크거나 같다는 조건이 만족되는, 작지는 않다. 요것도 사실은 또 증명할 수 있는 레머인데, 뭐 그냥 받아들이죠. 앤팩토리얼은 요거보다는 크거나 같다. 보면 다 됐죠. 최악의 비교의 수가 요거보다는 크거나 같다였는데, 그게 요거보다 크거나 같으니까 최소한 요거보다. 네, 그쵸? 요리에스윙증가.

이만큼은 최악의 경우 최소한 이만큼은 해야 된다 그것보다 더 적게 하면서 솔리팅을 완료할 수 있는 킥값에 비교해 solting하고 리듬은 없다 됐죠? 그래서 이건 n로그인 차수로 따지면 이건 n의 1승, n로그인 이니까 n의 1승보다는 높은 차수이고 order of eloge and, 그렇죠? "나옵니다"라는 거죠.

여태까지 우리가 만들어 봤던, 뭐, all's case 따지고 했을 때 제일 좋았던 알고리즘이 키각 비교를 통해서 하는 알고리즘이 data of n log n이 되었던 것이 우연이 아니었다. 그 보다는 더 좋은, order로 따졌을 때 더 좋은 알고리즘을 만드는 것이 불구하고 있기 때문에 그렇다라는 얘기예요. 그렇죠? 비교 횟수를 그렇게 그것보다 더 적게 하면서도 할 수 있는 차수가 따졌을 때 더 낮은 차수를 갖는

비교에 의한 솔리팅 알고 있는 건 존재치 않는다 라는 거죠. 그래서 이제 이 솔리팅 문제를 중점으로 중심으로 해서 그 어떤 알고리즘이든지 예를 들어서 뭐 비교를 통해서 하는 알고리즘에는 최악의 공원에 비교는 필요로 한다. 데이터 웬, 웬, 웬 만들 수 있는 제일 좋은 솔리팅 비교의 알고리즘 워스트 케이스로 따졌을 때 비교의 알고리즘이다 라는 거죠.

그래서 T장의 Sorting에 대한 그런 얘기들이 있었고 이런 식으로 결론에 해당하는 것을 보여주고 있어요. Sorting 문제에 대해서 특정한 알고리즘을 가지고 분석을 한 건 아닌데 어떤 알고리즘이든지 T값을 비교하는 것을 통해서 일반화해서 Decision Tree의 형태로 만들어서 Decision Tree의 깊이를 따짐으로 해서 깊이가 최소한 이 정도는 돼야 된다. 전체학의 경우. 이것을 보이는 방식으로 하는 거죠.

그 다음에 8장은 서치 문제에 관련해서 비슷한 방식으로 하고 있는데 시간 관계에서 한 문장 강의에서는 8장은 다루기가 어렵고 띄워서 9장에 있는 내용 그것도 오늘 다 알지는 못할 거고 오늘 할 수 있는 만큼 하고 나머지 강의는 동영상으로 목요일날 오늘 놓도록 할게요 자 그래서 9장에 있는 내용을 살펴보려고 하는데 9장의 제목이

theory of NP, NP 이론에 대한 소개되요. NP 이론. 그래서 여태까지 2장에서 6장까지는 실제 알고리즘을 설계하는 기법들에 대해서 우리가 쭉 살펴봤고 실제는 개개의 알고리즘에 대한 분석이 아닌 문제 전체를 놓고 봤을 때 알고리즘이 이러한 특징을 가지면

이러한 한계가 있다 라는 그런 방식으로 어떤 또 알고리즘에 대한 분석도 해봤고 근데 이제는 좀 더 그걸 확장을 해서 여태까지 여러 가지 문제들을 우리가 푸는 알고리즘을 많이 만들어 봤는데 어떤 경우에 대해서는 지금 이것처럼 뭐 워스티스 가 이만큼 보다 더 좋아질 수 없다 저에게 한계다 라는 것을 알고 있는 경우들도 있고 그런데 어떤 경우는

문제의 문제를 푸는데 한계가 어디인지 그거를 잘 모르게 되는, 모르는 그런 문제들도 사실은 있어요. 알고리즘이 과연 만들어져서 얼마큼까지의 오도로 내려갈 수 있을지에 대해서 모르는 문제들 그런 것들이 있는데 그런 것들에 관련된 것을 다루는 분야가 NPE 이론 분야예요.

트랙터블이 아닌 그런 개념이 이 인트랙터블이트라는 게 어떤 개념인지 하고 이걸 바탕으로 한 NP 이론에 대해서 소개를 하고 있는데 그거에 대해서 좀 살펴보도록 하죠 그래서 일단 인트랙터블이티라고 하는 거 이거는 뭐 트랙터블하다 라는 것에 인이 붙어서 그거에 반대 개념으로 쓰는데 뭐 보통 이제 트랙터블하다라는 거는 이런 컴퓨터 파악에서 쓰는 의미로서는 비교적 용이한 난해하지 않은 뭐 그런 의미로서 쓰고 인트랙터블이라고 하는 거는

상당히 복잡한 용이하지 않은 좀 난해한 뭐 그런 개념으로써요 자 그래서 이거는 어떤 문제에 대해서 이렇게 얘기를 하는데 이 문제가 인트랙터블하다 라고 하는 것이 무엇인지부터 정하죠 자 인트랙터블 문제라고 하는거 난해한 문제 예를 들어서 번역을 할 수 있을텐데 는 뭐냐면은 어떨 때 문제를 인트랙터블 하다고 그러냐면은 그 문제를 해결하는

Solinomial Time Algorithm, 다항 알고리즘이 없는 경우 그 문제를 다항 알고리즘으로 푸는 것이 불가능한 경우 그 문제를 Interactable 하더라고요 그러면 다항 알고리즘, 우리가 다항 오도로브 N제곱, 오도로브 N3성 이런 포리노미한 형태의 것들을 다항이라고 부르는 건데 다항...

시간, 번이름을 탐 알고리즘이라는 거는 정의를 하자면 인프크기에는 있을 때 알고리즘의 worst case behavior를 예를 들어서 다닐 수 있을 때 every case는 상관없고 아무튼 그 케이스가 나눠지는 경우 최악의 비교가 됐든지 같은 연산의 양은 필요로 하는 그런 경우 최악의 경우 이것이 Big O of PN 팔리로미언 형태로 되어 있는 PN의 Big O

속하는 경우 그거를 다항식한 알고리앱다 라고 해요 그래서 이 파리노멸이라고 하는건 엔에 대한 다항, k승으로 일반적으로 생각할 수 있는 것인데 그래서 우리가 알고 있는 많은 다항식들 엔에 대한 1승, 2, 참, 10승이 됐던 k승, 상수승 형태로서 변현되는 것 또는 사실은 우리가 일반적으로는 엔에 대한 다항식학으로 부르지는 않는데 이거는 차수의 개념으로 볼 때는 이

로그 N은 N의 1승 보다는 조금 낮은 차수의 그런 식으로 볼 수 있어서 N로그 N은 예를 들어서 1차와 2차 사이에 속하는 그러한 다항식의 형태다 라고 우리가 이 컴플렉스 딜을 얘기를 할 때 다항식의 일종으로 봐요 2의 N승 이런 것과는 차원이 다른 그런 것이니까 그래서 이 다항식에 해당하는 것 이런 것들까지 포함해서 다항식이라고 한다 인거고 폴리오미어 타임 알고리즘은

그 예들을 많이 봤죠. Insultence 오르다는 것. 그렇죠? N로그에 N제고, Sequential Search 그런 것들을 다 N-A 1차, N-A 2차 또 N로그에 이런 식으로 표현되는 그런 Complexity, 통신을 구했을 때 그런 다항식으로 표현되는 알고리즘 들이죠. 그래서 이런 Polyneum Time 알고리즘으로 해결하기 불가능한 문제를 Injectable Problem으로

자 그러면은 문제가 지금 인터랙터블하다 라는거 얘기를 했는데 그러면 우리가 일반적으로 어떤 문제든지 간에 이 세개의 범주 중에 하나다 라고 얘기를 할 수 있는데 자 어떤 문제는 그 문제에 대해서 폴리노멜 타임에 컴플렉스로 푸는 알고리즘이 이미 알려져 있는 그런 문제죠 우리가 지금 살펴본 아주 많은 문제들 쇼핑하는 문제, 솔치하는 문제

이런 것들은 또는 Shorty Spectre 찾는 문제, Minimum Sparing Treatment 하는 문제 다 다항차수에 해당하는 그런 알고리즘이죠 우리가 이미 문제를 푸는 데는 이런 컴플렉스티 다항차수의 알고리즘이 이렇게 있다라는 것을 알고 있는 문제들이에요 돌틴 문제 대표적인 거고 그런 유형의 문제들이 있고 그런 돈주에 속하는 문제들이 있고 또 어떤 것은

이렇게 펄이노메어 타임 알고리즘으로 푸는 것이 불가능하다. 펄이노메어 타임 알고리즘으로 문제를 푸는 것이 불가능하다라고 증명이 되어있어요. 수학적으로 증명이 되어있어요. 그런 문제들도 있어요. 그럼 어떤 것들이 그런 문제냐? 예를 들면 어떤 문제인데 아웃풋을 내야 되는데 아웃풋이 펄이노메어 형태로 그 N이 있을 때 N에 대한 폴리노미아 상태로

표현이 불가능한 그런 양 폴리노미아의 양으로서 불가능한 그런 양 아웃 자체가 그거를 만들어내는데 폴리노미아로 불가능한 폴리노미아 타임 예를 들면 우리가 앞에서 방법을 찾고 왔던 앵계의 키를 가지고 - 지금 보고.

테이션 5g 보게 되셨죠 모든 수령을 전을 을 아 그래서 이국들부터 배까지 에 100개의 숙제를 다 돈까지 된까지의 주제를 다 프린트를 하라 라는 문제가 있다면 그러니까 그럼 이것이 해야 되는 일에 약국은 얼마큼의 최소 9곳 하나씩 하나씩 프린트 하려면은 텍트 리얼 만큼의 예능을 해야 되죠.

그것보다 적게 할 수는 없어요 그렇죠? 하나하나 다 프린트 일을 하려면 그래서 그거는 펌 엔드펙트리아만큼의 일을 해야 되는 프린트를 하게 되어서 연산을 해야 되는 그런 것이기 때문에 엔드펙트리아는 당연히 펌에 놓으면 다행히 함수는 아니죠 그 다음에 모든 헤밍토니아 스로켓을 찾는 문제 그래서 그래프가 완전히 모든 두 개의

둘 사이에 다 연결선을 가지고 있다 라고 했을 때 그때 해빈톤이형 스킨을 찾는 문제 이것도 마찬가지로 n개의 키를 순서대로 나열하는 그런 방법처럼 동일하게 n팩트럴업 정도의 양은 모든 부분을 다 찾아야 되는 순서 이루탠 n까지 노드가 있으면 그 순서를 조합을 순서를 달리하면서 하는 방법이 n팩트럴업에만큼 있어요 그건 기본적으로 펀룸의 매력이 될 수가 없는 일의 양이다 라는 거죠 그래서 이건 이미

문제 자체로서 좀 더 맺한 바로 이 도대할 수 없는 문제 라는 것이 있죠 중용 택시 저는 문제인 것 꼭 이런 유형의 문제 외에도 예를 들어서 언 디사이더 부터 럼을 내고 해서 그 중에 뭐 대표적인 예로서 이 헌팅 파악을 위한 것인데 추인 프로 초인 머신 같은 것 얘기를 할 때 또는 뭐 일반적인 알고리즘을 얘기할 때 어떤 알고리즘이 예를 들어서 인풋을 받아가지고 그 인풋에 대해서 어떤 일을 해서 결과를 낼 텐데 그리고 결과를 내고 끝내면 할 텐데 예를 들어서 뭐 알고리즘이 어떤 식으로 작성이 되느냐에 따라서 엑스에 대해서

일을 하고 홀트 끝낼 수도 있고 중지 문제 터미네이트 알고리즘이 실행을 끝낼 수도 있고 아니면 무한무패에 빠지는 그런 경우가 생길 수도 있겠죠 무슨 뭘 받았냐에 따라서 또는 알고리즘이 어떻게 작성된 년에 따라서 그거를 결정할 수 있는 LP하고 X 받아가지고 EP라는 알고리즘 프로그램이 X에 대해서 홀트를 할 것인지 안 할 것인지를 결정할 수 있는 알고리즘이 존재하느냐

문제가 Undy Trider Problem인데 그거는 사실은 알고리즘 자체가 존재하지 않는 문제예요 우리가 생각하는 이 결정적인 형태의 알고리즘 자체가 존재하지 않는 문제예요 니까 이거는 알고리즘 자체가 존재하지 않는 거라면 그것이 포리념의 삶인지 아닌지 따지는 것 자체가 의미가 없는 그런 것이죠 그래서 이거는 포리념의 삶이 존재할 수 없는 그런 알고리즘이 존재할 수 없는 알고리즘 자체가 존재할 수 없는 문제니까 그래서 그거는

이 intractable이다 라고 증명이 되어 있는 문제예요. 이러한 작성을 가진 문제구나 이런 것들 이 대표적인 intractable에 해당하는 것이 intractable이다. 폴리너럴 타임 알고리즘이 존재할 수 없다 라는 것이 증명된 문제들인데 그럼 이거는 문제에 대해서 폴리너럴 타임 알고리즘이 이렇게 있다. 이렇게 하면 이 문제 이렇게 풀 수 있다. 그런데 높은 컴프넥스트가

하는 것입니다 라는 것이 알려져 있는 문제들도 있고 이렇게 그거는 도저히 불가능하다 발음을 탐 알고 있는 걸어서 푸는 것이 불가능하다라고 증명이 되어 있는 문제도 있어요 자 그럼 이게 문제 있을 수 있는 유형의 뭐냐 는 아니다 라는 거죠 문제 중에 이것도 아니면서 폰을 탐 알고리즘이 존재한다 라는 걸 알고 있지도 못하고 또 그렇다고 해서 이거는 폰을 탈으로 이 악을 띠이 있을 수가 없다 라고 증명이

그런 문제들 유형이 있는데 그게 이제 C번 유형이야 포리노멜탑 알고리즘이 존재한다 또 아니고 그렇다고 해서 존재치 않는다 라는 것이 이미 증명이된 조합적으로 증명이 된 문제도 아닌 그 중간에 족한 포리노멜탑 알고리즘은 모르는데 그렇다고 해서 존재치 않는다 라고 증명되지도 않은 그런 문제 유협들이 있다는 거죠.

그런데 그게 사실은 우리가 살펴본 많은 문제들이 여기 이 유형에 속하는 문제들이에요. 5번 랩스 문제는 우리가 많이 여러 가지 알고 있는 걸 만들어 봤죠. 근데 그 알고리즘 중에 펄리로밀 타임으로 분석이 되는 그런 알고리즘이 있었나요? 못 봤죠. 트랩은 세일이 프로젝트하고 또 펄리로밀 타임 알고리즘으로 푸는 그런 알고리즘을 본 적이 없어요. 다 알고리즘은 존재하지만 문제를 푸는 알고리즘은 존재했지만

분석해보면 다 나 버린 면 타임 기다리는거죠. m커러 랭프로 여러가지 다른 문제들 이러한 문제들 그럼 어떤 천재적인 인물이 나타나서 예를 들어서 오언제성 문제를 이렇게 해결하면 된다 라고 하고 알고리 들면 들었고 분석해보니까 폴리노미널 타임이더라. m의 케이스 형태로 표현할 수 있는 도도를 갖는 그런 것더라

그러면은 이런 유형의 문제에서 빠지겠죠. 이 문제는 아니다. 뭐 파리노멜타가 존재한다. 또는 뭐 어떤 수학적인 방법으로 이 문제는 파리노멜타가 알고리즘이 존재할 수 없다. 아까 전작들을 틀트하는 그런 것처럼 존재할 수 없다라는 것을 수학적으로 증명을 하면 그런 분할하는 건 이제 알 수 있을 텐데 미개덕으로 개트볼이구나 라는 걸 알 수 있을 텐데

현재까지는 문제들에 대해서는 이렇게 트랙톡을 하지도 않고 발림을 타물 분암으로 등이 발견된 것도 아니고 그렇다고 해서 불가능하다 존재할 수 없다라는 것을 증명한 것도 아니고 회색지대에 속하는 그런 문제들 그래서 NP 이론이라고 하는 것은 이런 것에 대해서 이런 문제들을 중심으로

문제 하나 가지고 이걸 펄일멜타임에 푸는 시도를 할 수도 있을 거고 아니면 그게 안 된다는 수학적인 증명을 시도할 수도 있을 거고 한데 아무튼 이런 문제의 집단을 가지고 연구들을 해서 개개의 하나하나에 예를 들어서 평생을 바쳐서 오원 랩슨 문제에 펄일멜타임을 타임 알고리즘을 만들고자 평생을 되겠죠 문 맞춰서 그거를 뭐 할 수도 있을 텐데

그것이 불가능하다는 것을 수학적인 증명을 하도록 노력을 할 수도 있는데 그런 것들의 노력이 좀 더 효율적으로 이루어질 수 있도록 집단적으로 생각했을 때 이루어질 수 있도록 이런 문제들이어서 여러 가지 성진들이라든지 이런 것들을 연구를 해서 해놓은 것이 NP 이론이라는 거예요. 그래서 NP 개념을 바탕으로 이러한 문제는 NP complete 문제다. NP 완전의 문제다. 또 NP hard의 문제다. NP 난의 문제다. NP easy 문제다. 등등의 여러 가지의 NP에 기반한 개념들을

이론을 풀어나가는데 9.4절에 NP 이론에 대한 기본적인 내용들이 나와있어요 뒷장에도 그거에 관련해서 여태까지 알려진 사실을 쭉 풀게를 하고 있는데 일단 NP라는 게 뭔지부터 얘기를 해야 될 텐데 일단 그거를 얘기를 하기 위해서 문제에 대해서 우리가 지금 문제라는 것을 가지고 얘기를 한다고 했죠 그 문제를 푸는 어떤 알고리즘인지 간에 한계 이런 것들에 대해서 우리가 얘기를 하는 건데 문제에 북한을 해서

얘기를 할 텐데 개별 알고리즘을 얘기하는 것이 아니고 문제를 중심으로 하는 거죠. 그런데 뭐 문제를 중심으로 했을 때 우리가 여태까지 살펴봤던 문제들 뭐 TSP 문제, Short-Spec Problem 문제 이런 것들 보면은 값 솔루션으로서 해로서 어떤 값, 숫자 값, 그렇죠? 또는 어떤 경로 이런 것들을 해로서 얻어내는 그런 것들을 생각을 했었는데 그럼 출력에 해당하는 값들이 그런 다양한 값으로 있을 수 있는 거죠. 어떤 스트링 형태도 될 수 있고 숫자가 될 수도 있고 뭐가

스위퀀스가 될 수도 있고 여러가지 일텐데 그거를 좀 단순화해서 출력 자체를 간단한 형태로 생각할 수 있는 문제를 한번 생각을 해보자 그래서 우리가 아까 디시전 트리 봤는데 그러면 디시전 트리 라는 거는 그 결정이 어떤 순서대로 나타나는 그런 것일 수도 있고 또 아니면 진짜 그 결정 값으로서 예스 노 라고 하는 그런 결정을 리프의 값으로 가질 수도 있는 형태인데

결정이 s 노란 아는 경우는 리프가 그 예수 노란에 가지는 그런 형태일텐데 그런 식으로 그 어떤 문제에 답으로서 문제를 해결하는 알고리즘이 있다면 그것이 내야 되는 출력으로서 가장 간단한 형태를 생각을 해보면 이런식으로 예수 노란 모축 볼 수 있는 그 dc 전에 해당하는 문제 그것이 그 어떤 알고리즘으로 내놓을 수 있는 그런 출력 중에 가장 간단한 형태다 좀 바이러 리

라고 생각할 수 있겠죠 여러 가지 다양한 형태의 해를 표현하는 방식에 비해서 yes, no, yes, no가 다 둘 중에 하나로 내놓는 그런 것이 있다면 즉 문제 자체가 결정을 답으로 하는 그런 문제라면 그런 알고리트 문제, 내야 되는 출력이 기시전이 될 텐데 그런 문제로 국한을 해서 생각을 해보자 그래서 디시전 문제라는 거, 결정 문제라는 거는

그 답이 문제에 대한 답이 decision로서 yes 또는 no로 되는 그런 문제가 이제 결정 문제에요. 그러면 우리가 여태까지 살펴봤던 뭐 TSP 문제, O1, Dapsack 문제 이것들은 다 Optimization 문제, 최적화의 문제였는데 그쵸 실제 뭐 배남의 아이템에 어떤 것들이 들어갔고 그 총 무게는 얼마고 등등 이런 것들로 패를 구하는 문제였는데 이거는 다

각각의 보원 앱슨 문제도 그렇고, TSP 문제도 그렇고 그거에 대응하는 디시전 문제로 대응시킬 수가 있습니다. 예를 들어서 트래블링 셀스 퍼슨의 옵티비제이션, 원래의 문제는 전체 그래프 주워놓고 그래프에 존재하는 행계 모드를 모두 방문하면서, 길이가 제일 짧은 경로를 찾는 문제, 제일 짧은 경로 그게 실제 솔루션인데

거 그 길이 깔 수 때 그 계실 수 있는 거 중에 제일 짧아야 되는 게 손짓인데 저를 오티미지에이션 그 오티미지에이션 원래 그 문제에 없으면 미지에이션 문제를 이 시절 문제로 생각을 해보면 그의 대응별로 띠시정되죠 예를 들어서 어떤 뒤 값을 이렇게 약속 값을 쳐놓고 뒤 값 보다 작가나 같은지는 경로가 존재하는 자 라고 묻는 그래서 다비하고 존재한다 아니다 라고 답할 수 있는 문제로 만들 수 있겠죠 좀 계속해 문제

서 그 경고 찾아 가지고 즉 제 최적의 넘는 사회 있을 때 어디 오카 보다 사망 되는 게 있다면 고 있네 이 딱 있겠습니다 하고 아니면 뭐라 전원의 경우 찾았던 이 보다 카더라 뭐는 워이거 노을 답을 하고 그 문제에 대해서 그렇게 할 수 있는 디시덕으로 제가 만들 때 음식에서 생각할 수 있고 뭐 한 액셋 문제도 마찬가지 좀 알까 뭐 좀 없고 그 프로필터는 프로필 시아 보다 커지는 그런 랩색 에 그 소스 되시 있느냐 좀 나이 들어서 없이 뭐 그런걸 묻는 문제 좀

그런 식으로 원래 옵티미지에이션 문제가 이렇게 디시적 문제화 그래서 답 자체가 yes, no로 나올 수 있는 문제화 될 수 있겠다. 대응시킬 수 있겠다라는 거죠. 못할 수 있겠다. 이런 값들을 줘 놓고 이렇게 문든 문제. 그랬을 때 지금 NP를 얘기하기 위해서 그러면 여기에 N은 뭐고 P는 뭐냐?를 얘기를 해야 되는데 그 P에 해당하는 것의 개념으로서 여기 P라는 것을 일단 먼저 얘기를 하고

그 다음에 그것을 바탕으로 NP라는 것을 얘기를 하려고 해요. 그래서 먼저 얘기를 하자면 P라는 것은 우리가 앞에서 얘기한 Polyneural Time의 그 P예요. 여기 뒤에 P도 마찬가지. 자 근데 이거는 그냥 Polyneural Time이라는 그런 개념으로서 정의하는 게 아니고 집합으로서 일단 정의해요. P라는 집합. 그러면 이 P가 뭐냐? 지금 우리가 결정 문제라는 걸 얘기했는데

알고리즘이 낼 수 있는 가장 단순한 형태의 출력으로서 Yes, No 결정을 내는 그런 알고리즘을 가지고 얘기를 하기 위해서 결정문제라는 걸 얘기를 했고 이 P라는 건 뭐냐면 디시전 문제들의 집합이에요. 지금 방금 얘기했던 결정문제 답이 Yes 또는 No로 나가야 되는 그런 결정문제들의 집합인데 그 문제를 푸는데 폴리노미어 타임으로 가능한 그 결정을 내리는데 폴리노미어 타임으로 가능한

그런 결정 문제들의 집합 그거를 P라고 불러요 파리노메 타임에 해결 가능한 결정 문제들의 집합 이게 P예요 P의 의미 집합이에요 결정 문제들의 집합 우리가 일반적인 문제로서 얘기를 할 수도 있는데 이론을 MP로 쭉 만들어 나가는 과정에서 문제 자체는 일단 결과가 달순화해서 바이너리로 이렇게 나올 수 있는 그런 결정 문제로 북한 시켜서 생각을 하고 그걸 바탕으로 쭉 이론을 만들어나가는 것이 일반 문제를 가지고

그런 것을 다 통합할 수 있는 그런 방식으로 이룰을 만들어 남아가는 것에 비해서 훨씬 수학적으로 간결하고 그리고 그렇게 결정문제로 한다 하더라도 일반 문제로 했을 때 얘기할 수 있는 것과 사실은 능력적으로 동일하게 얘기들을 할 수 있기 때문에 이렇게 디시전 문제 북한 시켜서 일단 하는 거고 아무튼 P라는 것은 디시전 문제들이 집합 결정 문제들이 집합이다. 그렇죠? 그 결정 문제를 푸는데 Perlm-Altime으로 가능한 Perlm-Altime 알고리즘까지는 결정 문제들이 집합 그러면 결정 문제로서 예를 들어서 어떤 키가 어떤 array 안에 있느냐를 묻는 문제 어떤 키 주고 어떤 array 주고

그 P가 array 안에 있느냐? 결정을 내리는 예수는 으로 내리는 문제. 이거는 뭐에요? Punting-Maltym 알고리즘의 해결 가능하죠. 엔게의 값들이 있는 array라면은 worst case, 오늘 or when의 비교를 통해서 할 수 있는 그런 문제니까 답을 낼 수 있죠. 이건 P에 속하는 문제에요. 결정 문제로서. 그 다음에 어떤 array가 solt 되어 있느냐를 묻는 문제. solt 하는 것 자체는

안 되게 시키기 값의 비교에 의해서 한다면 오더로 뱀 로그에 내고 그래서 그걸 그냥 확인하는 일만 한다고 하면은 오더군 m 에 가능하죠 첫 번째가 두 번째 오자 그냥 두 번째가 제거 두고 다 차가운 앱 공부 n - 1 것 개 비교를 통해서 잡을 낼 수 있어요 그 중에 하나라도 아니면 속도 있지 않은 거니까 그래서 그것도 피해요 좀 좀 내내 아니까 아 아 아 아 아 자 그러면은

이런 간단한 문제들, 이것들은 피에 속하는 문제들이 다 알 거라는데 그러면, 아까 얘기했던 TSP Decision Problem 또는 O1Napsack Decision Problem 이것은 피에 속하는가? 이것을 푸는 앞의 문제 또는 O1Napsack 문제, 이것을 푸는 터리노임템 알고리즘이 있는가? 따져보면, 일단 수업 시간에는 그런 것을 배운 적이 없고, 실제로

여태까지 알려진 판네럴탐인 알고리즘이 존재치 않는 문제들이에요. 아까 얘기했듯이 CU형의 문제에 속해요. 그래서 이 문제들은 당연히 피에 속한다 라고 얘기할 수는 없는 그런 거죠. 모르는 거죠. 속하지 않은 문제 사실은. 그렇죠? 존재치 않는다라고 증명하지는 좀 하는 것도 없으니까. 플레이널탐을 알고리즘이 존재합니다.

지 모르는 거예요 여태까지 우리가 알고 있는 분 알고 있는 다 그게 아니었던 것이지 혹시나 누군가가 또 새로운 날 보리도 하나 만들어주고 문제를 통인데 제대로 풀고 또 파리 를 타이밍 뭐 그러나 그들 만들었다면 그때는 이제 아 이 용부에 열어주시면 되는 피해 속하겠구나 왜냐하면 파리 를 담아 알고 있음은 그렇죠? 알았으니까 그런 게 없겠지만 현재까지는 그 누구도 그런 알고 있는 걸 만든 적이 없다

그래서 뭐나요? 피해있는지. 그렇죠? 그래서 이런 것들은 일단 피해있지 않고 이런 문제들은 피해있고 피해있는지 없는지 모르는 거죠. 피해있지 않고는 아니고 피해있는지 모르는 문제죠. 피해있다는 것을 알고 있고. 그렇죠? 피해있는 피해있는 것들은 피해있는 것들은

알려지죠. 발견된 디지털 프로그램에 집합이다라는 거고 그러면 이제 MP라는 것에 대해서 MP론이니까 MP라는 것에 대해서 얘기를 해야 되는데 여기 MP에서의 P도 폴리멜탈이에요. 폴리멜탈 P가 나타내는 의미와 사실은 같은 P인데 그러면 N은 뭐냐 난 deterministic 비결정적인

그래서 디테미니티 결정적인 결정론적인 그런 그런 알고리즘에 대해서는 우리가 지금 사실 여태까지 쭉 살펴버리는 알고리는 다 그런 결정적인 결정론적인 알고리즘 들인데 그것이 아닌 형태의 결정론적인 알고리즘이 아닌 형태의 어떤 알고리즘을 우리가 이제 생각을 해볼 수 있는데 비결정론적인 알고리즘이라고 하는 비결정론적인 알고리즘입니다.

그래서 비결정론적인 알고리즘으로 파리노메일 타임에 해결 가능한 결정문제들의 집합 그게 NPM 그래서 비결정론적인 알고리즘이라는 게 뭐냐를 정리하기 위해서 누가 주장한 솔루션에 대한 검증 이게 진짜 솔루션이다 어떤 문제에다 솔루션이다 을 검증하는 그런 과정 이런 것들이 사실 이제