[난제] PNP 문제

[@lsy_math]

인트로를 삭제하였습니다.(2021.06.18) 그로 인해 기존 영상과 약 9초의 시간 차이가 발생하였으니 참고해주세요.

[@김지후-q3w]

2년전 영상이지만 아직도 이 양상을 관리하시다니 ㄷㄷ

[@fullsoul4619]

이런 띵강에 좋아요를 한개밖에 누를수 없다는게 화가난다

[@김한웅-r2k]

full soul 그럼 두번을..

[@고휘릭그는곧전설이될]

인죵 인죵

[@ovob123]

ㅇㅈ

[@dipskim9638]

인정입니다

[@딴재미벌레]

n이 자연수일때, 2n-1번 누르세요

[@ma_toto]

와 울 교수 버벅이면서 설명하는거 듣다가 속이 막혔는데, 시원하게 이해하고 갑니다

[@user-sangbeom_kim]

여태까지 본 강의 중 어려운 내용을 가장 쉽게 설명해주시는 분입니다. 감사합니다^^

[@BillPark-ey6ih]

수학에 호기심이 많아 영상을 자주 챙겨보는데 이제서야 구독누르네요. 이런 어려운 내용을 알아듣기 쉬우면서도 정확한 방향으로 설명하는게 이 채널의 장점인듯 합니다.

[@skyinthe908]

어디서 이런 어려운 내용을 이리 쉽고 자세히 설명해줄까요 넘 재밌고 쏙쏙 들어옵니다 ㅎㅎ 강의 중간에 하시는 말씀처럼 타 강의들은 무슨말인지 와닿지 않는 내용이 많으나 설명을 안해주고 넘어가니 그 뒤부터는 이해가 안되 결국 듣다 안들려서 흥미를 잃고 포기하게 됩니다 수학과 관련 없는 개인 사업자이지만 넘 재밌습니다

[@hyunwoolee3848]

지금까지 수많은 P-NP 설명을 들었지만 가장 이해하기 쉽게 설명해주셨습니다. 존경합니다..!!

[@김지운-r2e]

대단한 설명과, 문장 문장 사이의 공백을 편집으로 없앤 디테일 매 번 감탄하고 갑니다.

[@jonghopark8185]

우리 학교 김교수가 두 시간 동안 수업했을때 이해 못했는데 이 영상을 보고 이해가 되네 ㅋㅋ

[@전성훈-c1m]

감동입니다 진심 감사합니다 선생님 양질의 강의를 무료로 배포해주셔서

[@dlim9696]

미국에서 컴퓨터 과학 석사과정을 공부하는 학생입니다. 학부시절때부터 알고리즘에 너무 관심이 많았어서 알고리즘 해석 디자인 수업들을 제일 좋아했었는데 이렇게 다시 상엽쌤 소개로 접하니까 너무 반갑네요 ~

[@이선비-k6w]

질문이 있습니다. 만약에 어떤 NP문제가 여러 NP문제로 나눌 수 있으면 그 NP문제도 NP-난해문제인가요? 그러니까 예를 들면 13:51 에서는 문제 A, 문제 B, 문제 C, 문제 D 가 있는데 B, C, D 를 문제 A로 환원이 가능해서 문제 A가 NP-난해 문제인것이잖아요. 그러면 원래는 문제 A밖에 없는데 그 문제를 문제 B, 문제 C, 문제 D로 나눌 수 있다면 그 문제도 NP-난해 문제라 보는 건가요?

[@nyamnyam5780]

설명 너무 잘하시는데요. 왜 이런 퀄리티의 영상 조회수가 이 정도 밖에 안 나오는지 매우 의아합니다.

[@Gabibing]

개인적으로 공부하고 있는 문제였는데 이렇게 올려주셔서 감사합니다.

[@KOREAyoungwoo]

설명 들은 것 중에, 최고네요 감사합니다 구독합니다!

[@yhcsm7180]

와... 존경합니다 모든 강의가 제 지식수준발전에 도움이 되고있습니다

[@이승한-c6d]

소리도 좋고 내용도 좋아서 아침에 운동 갈 때 돌려보고 있어요

[@서울촌놈-k6y]

선생님의 식견에 매 번 감탄합니다ㅠ 한 해의 마지막 날 쩌는 강의 올려주셔서 고맙습니다. 덕분에 뭔가 뿌듯한(?) 2018 마지막날이 되는 듯 하네요 ....

[@김형수-l4z]

영상의 질이 매우 높네요!! 응원합니다

[@dipskim9638]

헉..너무 재밌어요ㅋㅋㅋ 시간가는 줄 모르고 시청!

[@junck2381]

짧지만 명쾌하네요. 예시들이 많이 도움이 되었습니다. 구독자 한명을 얻으셨군요 :) 이런 흥미로운 영상 계속 부탁드립니다!

[@민경민-h7p]

선생님 설명 정말 잘 해주시는거 같아요 얼마 전 리만가설에 관심이 생겨서선생님 동영상을 처음 접했고 말만 들어보던 p-np문제가 무엇인지 궁금해서 이 영상도 보게 되었는데 이런 좋은 영상 만들어주셔서 감사합니다

[@royradiant]

학부 시절에 여러 소트들을 배우면서, 시간 복잡도가 어떻게 유도되는 지 몰랐는데 여기서 알게 됐네요. 감사합니다.

[@Snowflake_tv]

우와 이번 영상 완전 취향저격! 우연의 웅덩이에서 그렇게 될 수 밖에 없는 연결고리인 필연을 찾아가는 과정... 이런 거 좋아요 ㅋㅋ 꼭 마법주문 찾는 것 같거든요 ㅋㅋ

[@Level6]

훌륭한 강의 감사합니다. 'NP-완전과 P는 다르다'는 학자들의 예측 소개해주셔서 감사합니다. 각자의 위치에서 최선을 다하다 보면 언젠가는..!

[@정윤석-r6k]

와 정말 좋은 강의네요ㅠ_ㅠ 감사합니다 다음 번에는 시간 더 길어지더라도 좀 더 많은 내용에 대해 듣고싶어요

[@이선비-k6w]

np 난해문제가 무슨 문제인지 궁금하여 p np가 뭔지부터 알려고 인터넷에 검색했더니 다 알수없는 말들로 잔뜩 써져 있더군요. 이렇게 쉽게 설명해주어 감사하오.

[@하이퍼수학]

이론은 되게 어려운 듯 한데 예시들을 너무 잘 들어주셔서 그런지 거진 다 이해됐습니다!! 재밌네요 ㅎㅎㅎ 수학의신님 새해 복 많이 받으세요!!

[@koreaorang2351]

제가 본 p np 강의 중에서 가장 알기 쉽게 설명해주신거 같습니다 감사합니다

[@Snowflake_tv]

이 쉽다는 것도 저는 3번 본듯 ㅠㅠㅋㅋ

[@mathboy5660]

너무 잘봤습니다 항상 감사하게 보고있어요~😊

[@doordoor5278]

잠오기 전 이선생님의 영상보면서 잠이들곤하는데 이렇게 잘설명해주시는분이 없다고 해도 과언이 아닌것같습니다 ㅋ 2018년 마무리 잘하셨을거라 생각하고 내년엔 더욱 번성하세요. 그리고 영상올리실때 퍼센테이지 다올라가졌다고 바로 (게시)눌르지마시고요 좀더 기다리시면 고화질로 업로드 됍니다.

[@ljh55382]

PNP 접합, NPN 접합..트렌지스터 인줄...

[@wintrover]

엌ㅋㅋ

[@junminkim4506]

올려주셨군요! 감사합니다ㅠ

[@물리학-c8m]

김상엽 선생님 유익한 강의 감사합니다. 요즘 취미로 선생님 강의를 포함하여 수학 강의를 듣고 있는데, 사고력이 갈수록 함양되어 가는 것 같아 좋네요^^

[@김민국-j9e]

수학에 관심이 많은 직장인입니다. 이 분 뭐하시는 분이시죠? 너무 재밋게 강의해주시네요ㅎㅎ 수학관련 재밋는 책이나 본인이 쓰신 책 같은게 있으시다면 그와 관련된 영상을 올려주시는 것도 좋을 것 같습니다ㅠㅠ 조회수 너무 작아서 의아하네요 정말;;

[@Snowflake_tv]

주제가 수학이라서 그래요 ㅋㅋ 그리고 칠판 앞에서 하시잖아요. 저도 학창시절땐 수학점수 너무 안나와서 싫었어요 ㅋㅋ 수학 자체는 저도 잘 하고 싶었는데, 수학점수가 거지였음 ㅋㅋ

[@Arm-wrestling]

앞으로 무럭무럭 성장할 채널이 될 거라 확신 합니다 ^^ 정말 재밌고 유익해요 .. 저도 나이가 많지만 .. 다시 정수론 공부를 시작할까 생각중입니다..

[@honguy75]

감사는 제가 드려야죠 오늘도 하나 배우고 갑니다.^^~

[@chaffle7265]

설명이 되게 간결하고 깔끔해서 좋네요 ㄷ

[@kkj3947]

17:45 다르지만, n!을 n과 m의 다항식 조합으로 쪼개서 곱하는 방법은 찾았어요. 자신 없긴 한데 억셉 되면 좌표 줄게요

[@rhfnaaps37]

정말 유익합니다. 좋은 영상 감사합니다.

[@이명준-g1f]

이걸 지금 봤는데 3년전 강의가 더 설명이 좋네요. 대박..!

[@정영균-v6s]

상엽 선생님 응원합니다!

[@띠용-l3j3r]

컴퓨터 전공하는데 P=NP가 뭔지 잘 이해가 안갔는데 이 영상보고 어느정도 이해가 갔습니다. 나중에 또 보러 오도록 하겠습니다 감사합니다!

[@이상원-s2l1y]

꼭 밀레니엄은 아니더라도 학교 수학시간에 상엽쌤처럼 교양적인 수업도 해야하는데... 가끔 ebs 딸랑 보여주고 끝내구..

[@rnjsaudwo]

훌륭합니다. 짝짝짝...

[@ek_tango]

잘 들었습니다. 좋은 강의 감사합니다.

[@martinokim5543]

휴리스틱을 배우면서 이걸 공부하게 되더라고요. 여기서 만나니까 좋네요 ㅎㅎ.

[@yegipark4803]

너무 잘봤습니다. 감사합니다!

[@이선비-k6w]

질문이 있습니다. 17:25 의 다이어그램을 보면 NP와 NP-난해의 교집합이 NP-완전이라고 되어있는데요 그 다이어그램만 보면 P=NP-완전이라 해서 P=NP가 아니지 않나요?

[@divergence8549]

NP완전집합은 모든 NP들의 상위호환이기 때문에 NP완전이 P임이 증명되면 자연스럽게 NP도 P인것이 증명 되는거죠

[@use-hvchnk]

잘 보았습니다. 반도 이해할듯 말듯한데 여러번 봐야겠네요. 그냥 저는 20여년전 대입을 본 일반인입니다. 이런 강의 올려주시니 매우 감사합니다. 이정도로 쉽게 설명하시는 것도 대단한 재능과 통찰입니다. 그런데 이런수준의 내용이 요즘 고등학생을 위한 강의인가요?

[@전민제-i5i]

중학생도 재밌게 보고있습니다^^

[@송저씨]

잘보고 있습니다~ 감사해요

[@syldris]

PNP 트랜지스터 인 줄 알고 들어왔습니다. 재미있게 보겠습니다.

[@액티비아]

감사합니다. 강의 듣다가 time complexity가 나와서 몬가했는데 명쾌하네요

[@ryanpark1107]

잠이 오지 않을 때 보면 좋을 듯하다.

[@featherstones6766]

16:32 듣다가 궁금증이 생겼는대요. NP 완전 집합은 결국은 NP 난해 문제와 NP문제의 교집합이라는 말씀이신데 NP완전이 P 집합이나교 묻는것은 P집합이 NP집합의 부분집합이냐는 뜻이 아닌가요?

[@jihochoi_cs]

저희 학교 교수님이 이 영상을 봤으면 좋겠어요...

[@이머꼬-m9g]

60대 청춘이 보는 동영상으로 좋아요~

[@tkdwns729]

여러분들 참고로 슈퍼 마리오 브라더스가 NP-난해 문제입니다(..). erikdemaine.org/papers/Mario_FUN2016/paper.pdf

[@무지개앵무새]

와 진짜 설명 미쳤다 ㅋㅋㅋ

[@김수연-r8c]

좋은 강의 감사합니다~~

[@퓨리에]

감사합니다!!

[@yj1040]

!

[@moonshadow1177]

이야 깊이가 남다르다.

[@youtubepublisher6309]

와... 백날 위키백과 봐도 뭔 개소린가 했던 문제를 이렇게... 감사합니다.. 제가 P-NP문제를 이해할 수 있는 알고리즘이 NP문제였었는데 덕분에 P문제로 거듭나 차수마저 엄청 떨어졌습니다.

[@sjch7899]

대학생 대학원생이 봐도 재밌어요~ 수학과를 갔어야햇어...공대 노잼이에요...

[@박준형-q7n]

근데 막상 전공으로하면 머리터질듯 ㅋㅋ

[@kimkyle4607]

학부때 교수님이 나비어스톡스 해 구하는 연구에 대한 내용들로 강의를 해주신적있는데 그뒤로 수학을 가슴으로 받아들이게 되었습니다.

[@TureTaegee]

컴공과에서도 형식언어 오토마타나 알고리즘 시간에 저런 계산복잡도에관한 공부해요 꿀잼입니다

[@KRFile]

소프트웨어전공자인데 시간복잡도나 버블정렬에 대한 얘기도나오는군요.. 잘봣습니다~

[@skokieh]

감사합니다.

[@무늬없는기타]

설명 정말 잘하심 !!!

[@이제뭐하지-j2o]

만약에 p=np문제가 p=np가 참임이 밝혀지면 np를 p문제로 해결하는 방법을 묻는 문제나 np문제해결 시간소요를 최소로 줄이는 방법을 묻는 문제 등이 나올거 같네요

[@kunhyungtwicebamm2860]

초전도체로 시간복잡성이 풀리는 구조가 될수있어 다항식의 지수시간이라는 개념이 신소재로 다시 경계를 바꾸는 문제가 될수도 있네요. 이해를 확장하자면 다항식의 지수시간이라는 알고리즘의 한계가 다른 방식으로 풀릴수 있는 가능성을 본거죠. 물론 암호학의 형식 논리는 그대로 남거나 다른 방식으로 무력화 할수 있긴합니다. 완전히 원점에서 다시해야할 수도 있구요. 수학에서 꼭 기억해야할 공리적 사실은 보는 문제의 경계를 어떻게 공유하느냐의 핵심이 남긴하네요. 동일한 커피 두잔이 있는데 이 두가지의 차이점은 엔트로피일수도 있어서 에너지가 차가운 곳으로 흐르는 방식을 설명할 수는 있죠. 수학은 물리학과 관계에서 이 문제를 보정받거나 보정을 해주는 역할로 섞여있네요. 컴퓨터 공학의 문제는 신소재의 기술로 바뀌고 양자컴퓨터도 역시나 같은 원리로 바뀌는데 이 문제를 정보로 환원되는 구조네요. 물리학에서는 관측에서 측정 범주를 줄이다 확률로 설명한 문제이고 bit라는 정보를 쓰거나 퀀텀비트가 되는거죠. 다항식의 지수시간 알고리즘 원리중 재밌는 형식이 하나 있습니다. 초전도체가 사실이라면 시간복잡성으로 경계를 다시 정하는 방식이 있지만 풀리는 방식이 바뀌죠. 현재 양자컴퓨터의 알고리즘이 조금 이상하다는 생각이드네요. 다면체 문제 중에 이 문제를 보다가 양자컴퓨터 알고리즘 문제가 딱히 없다는 결론과 구성력이 떨어지는게 아닌가하는 의구심이듭니다. 수학적 다면체중 실제 확고하게 양자컴퓨터 중첩원리보다 더 정확한 이해를 가질수 있는 실재를 만드는게 아닌 실제가되는 원리가 있긴 합니다. 양자컴퓨터의 정확성을 어떻게 내세우느냐에 따라 답이 갈릴듯 보이네요. 확실하다는 말은 없는거지만 재밌는 결론이 나올수는 있어보이네요.

[@kunhyungtwicebamm2860]

질문을 하나 하고싶은데 수학에서 보는 co-np는 어떤 의미인지 co-np완전은 무슨 의미인지 입니다. co의 의미가 어떻게 가둬지는지 아주 의미있는 대답을 듣고 싶습니다. 푸앵카레 페렐만의 정리처럼 일반화의 문제인지 알아야하는 것이죠.

[@복실이와삼부자]

5:49 에 6번이 아니라 7번이 되었네요ㅋㅋ 6번째꺼는 빼야 될 것 같아요

[@yjg7153]

이런 채널이 10만 구독자도 안 된다니.................

[@chungjae12]

Complexity를 이렇게 예쁘게 정리해서 설명하는 영상을 많이 못 본것 같아요. 정말 감사합니다 :) 배부른 부탁일 수도 있지만 혹시 reduction 예제들을 모아서 설명하시는 영상도 있나요..? 선생님의 생각을 듣고싶습니다. 항상 응원합니다. 많이 배워갑니다. 감사합니다 :)

[@mqndlps8146]

이해가 안가는 부분이 17:20에 p=np-완전 이랑 그 옆도 같지 않다는거 그냥 p=np아닌가요 집합 그림만보면 np-완전은 np-난해와 np의 교집합인데 np-완전과 p가 같다는게 그림과 매치가 안되서 ...

[@jhs1530]

P=np-완전이면 모든 NP문제들이 NP-완전으로 환원가능하기 때문에 P=NP가 되겠죠?

[@0.original563]

재미있네요~

[@hhh-pd1rn]

푸앵카르의 정리도 한번 다뤄주시면 굉장히 흥미로울 것 같아요!!!

[@brianbrian4899]

05:37 n * (n+1) / 2맞지 않나요?? 3의 경우 3 * 4 / 2 즉 6 = 1 + 2 + 3 4의 경우 4 * 5 / 2 즉 10 = 1 + 2 + 3 + 4

[@안성하-b5d]

원소가 N개 있을때 1부터 N-1까지 합 입니다

[@아아아-i5q6g]

정렬알고리즘 배우면서 스치듯 지나갔던 pnp문제가 이거였구나..

[@x8359]

ppap랑 비슷한건가요

[@Snowflake_tv]

수신쌤도 나중에 유투브 정리한 책 한권 집필해보심이 어떠세요? 솔직히 주제가 수학인지라, 잘 팔릴지는 확신이 안 서서 제가 막 권유하긴 그렇지만,,, 혹시 몰라요? 출판비가 부담되면 이북으로만은 낼수는 없나... 비용이 좀 적게 들 것 같아서요. 그리고 수신쌤은 영어도 잘하시잖아요. 자막 보니깐 실수만 빼면 진짜 교과서처럼 완벽하시던데.(영어본을 넣는 이유는, 아무래도 영어유저수가 많으니 시장이 넓어지잖아요. 못하시는것도 아니니까.) 한국어랑 영어로 e북으로 출판해서 패시브인컴을 구축해보심이...ㅋㅋ 너무 내용이 좋아서요. 쿠키님도 책 내신 거, 솔직히 시청자 입장에선 흘러가는 영상에 대해서 붙잡아놓고 기억하고 메모하는 용도로 써먹기 좋거든요 ㅋㅋ. 물론 저처럼 지식을 붙잡고싶어하는 사람들에 한해서요(그럴 시간과 의지가 있는 인구가 얼마나 많을진 모르겠지만) 진짜 쿠키님 책 내신 거, 인강 교재 개념의 큰그림이라고 생각합니다.ㅋㅋ 근데 이건 제 바람이지, 사실 없어도, 그냥 노트에 적어놓으면 돼요 저는. 아무튼 여러 요소 고려해보셔요. 수신쌤, EBS같은데에 고정출연 하시고 유투브 홍보하신다음에, 나중에 10만명 넘어가고 책 출판하시면 캬... 남걱정할때가 아닌데, 내 패시브인컴이나 만들어야할텐데 ㅋㅋㅋ 큰일일세

[@wdcm3995]

용의자x의 헌신에 있던 문제인가요?

[@Study-cs5zs]

그러면 P문제는 재귀함수에서 자기자신을 한 번 호출하는 문제이고, NP문제는 재귀함수에서 자기자신을 여러번 호출하는 문제군요?

[@김연진-t7p]

NP 문제가 아닌 암호체계가 있을까요? 암호의 조건(제 개인적 생각) 1. 입력된 암호와 답이 일치하는지를 빠르게 검사할 수 있다.(검산의 시간복잡도가 다항시간이다.) 2. 모든 경우를 다항식 시간복잡도 안에 검사할 수 없다.(입력크기에 대한 경우의 수가 다항 시간보다 크다. 예: 지수)

[@1f5d0dc68c]

암호는 np문제 일 수 밖에 없습니다. 암호가 답이 (key)가 주어졌는데 사용자가 그걸 빠른시간안에 풀지 못하면 결국 key를 모르는 공격자와 차이가 별로 안나겠죠

[@wintrover]

와 설명 너무 잘하시네요

[@달하-h4x]

알고리즘 수업에서 이해 못한걸 여기서 다시 깨닫습니다

[@atlantiscolors4491]

저도 한동안 생각해 봤던 문제,, 제 결론은 현재 컴퓨터 구조는 P, 양자 컴퓨터 구조에서 가능한 NP

[@sangtaelee698]

양자컴퓨터가 블럭체인 공식으로 풀어줄거에요

[@goodandtak1331]

괴델로 연관해서 추천되었나...... 무한 선택공리 집합론 수리기초론 수리논리학 기호논리학 메타논리학 양상논리 가능세계 형이상학

[@dame4337]

모든 NP문제는 해결가능하고 NP난해 문제는 해결 불가능하거나 해결 가능한지 불가능한지 모르는 문제라고 이해했는데 맞는건가요?

[@PlanCoim]

개꿀잼이에여

[@Snowflake_tv]

제가 결정론적 튜링 기계입니다.ㅠㅠ 그나저나 오름차순으로 만드는 알고리즘을 돌리는데 걸리는 시간이 등차수열의 합으로 나타나는게 신기하네요. 맨 뒤로 보내게 되는, 가장 큰 숫자가 가장 확실하게 맨 뒤로 가게 되는 현상이라... 흠...

[@이민규-p4p]

제가 이분 영상 처음봐서 그런데 혹시 이 분 전공이 어떻게되시나요 알고리즘 시간에나 배울 내용인데 ㄷㄷ

[@서울촌놈-k6y]

수학과이심.. 멘사츨신이시고..

[@김감독-d1u]

나비에스톡스도 한번 다뤄주세요 ㅜㅜ

[@강철-r6k]

선생님 인테그랄 0부터 무한 까지 x^p/1+x가 수렴하는 실수 p의값이 존재할까요? p가 양수 일때는 발산한다는것 까지는 증명이 가능한데 p가 음수일때는 발산할지 수렴할지 알수가 없어서 선생님께 질문 드립니다.

[@Gktjddnd1]

0

[@jj-dn6vr]

모든 지수함수를 다항함수로 변환할수있다는 걸 증명하는거랑 같은얘기인가요? 궁금하네요

[@shyofshyness]

선생님 퓨리에 변환에 대해서 한번 정리 해주시면 안될까요

[@barnumeffect9422]

음...세계 7대 난제답네 리만가설이랑 푸엥카레 정리 빼고는 오로지 공식 외엔 설명조차 안된다더니 역시 나의 대뇌가 절망적 신호를 보내옴

[@올빼밍밍]

ㅠ 띵강이다 ㅠ

[@김대종-q5r]

흐으응미로워욘

[@MATHONG]

선생님 영상 잘보고 공부했습니다. 제가 고등학생인데, 이 문제를 보고 생긴 궁금증을 스스로 생각해봤습니다. 근데 분명 틀린 결론이 나온 듯 한데 스스로 어디가 틀린지 알수가 없어요. 주변에 여쭐 분도 없습니다. 선생님께선 혹시 이런 문제가 생기면 어디에 물어보시나요?? 외국 사이트를 써야하나 싶네요

[@taero4161]

나의 빛,,,

[@karlpostlove1]

우리 아빠 회사 아님?