PNP문제 알아보기

[@고영민-d5m]

이 문제를 보면서 머신러닝에서 신경망이 떠올랐어요 단순한 선형결합을 non-linear한 function을 거치는 과정을 수없이 반복하는 게 우리 세상에 풀기 어려운 NP문제를 P문제처럼 단순화해서 컴퓨터가 반복해서 계산해나가는 과정인 것 같은 느낌이 들었습니다

[@leetae-kyoung1084]

좋은 관점입니다.

[@고영민-d5m]

@@ijlijl1ijl1i 공부를 더 해보니 그런것들이 approximation이라는 큰 분야에 부분들임이 보이더군요 푸리에 시리즈, 푸리에 변환 , 확률적관점에서 다항회귀 등 다루기 어려운 세상 관심사를 다루기 쉬운 함수들로 근사화하는 인간의 한계이면서 상식적인 것들의 출발이 보이는 즐거우면서도 해결해보고 싶은 주제입니다

[@별나라에서온루비]

NP 알고리즘을 이해할 수 있게되었어요.

[@jihwanchae6040]

이런 유튜버가 진짜 전문유튜버

[@Son-lm5mf]

진짜 너무 좋은 영상입니다 !!!!!!

[@이정현-k4o8k]

오오 좋은 영상입니다 감사합니다~

[@Anonymous-kj6cu]

예시를 알기 쉽게 들어준 게 좋다.

[@leetae-kyoung1084]

아주 좋은 영상입니다. P, NP에 대해, 이해하기 쉽게 풀이한 영상입니다.

[@numbincobay3094]

좋은영상감사합니다.

[@한정인-t1s]

p=np라면 다항시간내에 푸는 알고리즘을 찾는 것이 어려운 문제라 할때 np이고 이또한 p로 바꿀수 있다는 말이므로 찾는것이 쉬워야 하지 않나요?

[@에마109]

오 너무 재밌게 잘 보았습니다. PNP 문제 .. 연구를 해서 결실만 맺으면 부와 명예를 동시에 가질 수 있는 주제네요 .. ㄷㄷ

[@전금조-f6h]

주제가 신비해 생각날 때마다 가끔씩 들어옵니다! 혹시 영상에 사용된 배경음악 출처를 알 수 있을까요?

[@익명-c8h3h]

구독합니다

[@이지후-b6x]

영상이 너무 유익해요ㅠㅠㅠ 혹시 2:05 부분에서 쿠르트 괴델이 존 폰 노이만에게 편지를 썼다는 정보는 어디서 찾을 수 있을까요???

[@snowlime_kr]

8:48 솔직히 n이 2면 되거든요

[@바나나초코파이]

3:07 에 NP문제의 정의가 비결정론 튜링기계를 사용해 ""다항시간"" 내에 답을 구할 수 있는 문제의 집합이라고 나오는데요. 6:26의 예에서 특정부분집합의 합이 0이 되는지의 문제는 다항시간이 아니라 "지수시간"인데 왜 NP문제인 건가요? 혹시 쉽게 설명해주실분 계신가요...

[@kakyeon]

영상에서 설명이 잘못되었습니다. “지수시간” 문제와 “비-다항시간” 문제는 같지 않습니다. 다항시간 < 비-다항시간 < 지수시간 이런 순서로 되어 있으며, P vs NP 문제는 다항시간과 비-다항시간 문제 간의 관계를 묻는 것이지 지수시간의 문제를 묻는게 아니죠.

[@MATHONG]

비결정론적 튜링 기계는 다음 행동이 여러 개거나 없을 수도 있다는데 1개 이상은 틀린 설명 아닌가요?? 물론 이 영상에서 크게 중요해보이진 않습니다.

[@wohwjde9274]

마스터키를 찾는 여정이군요

[@김은영-d7j]

수학의 난제는 완전하다~

[@이재현-s1t9u]

문제를 주고 답을구했을때...즉 2+2=4...답을주고 문제를 구했을때...즉 4=1+3, 2+2...그러니깐 2+2=4와 4=1+3, 2+2와 같음을 수학적으로 증명하라...이건가???

[@이상한변호사우병-g3b]

그걸 풀수있으면 완전한AI가 생기는거임

[@겸손은기본-i6z]

같음을 증명하라는게 구체적으로 (너무 성의없는 예시이긴 하지만;;) n문제 '2+2=4'는 np문제 4=1+3,'2+2'....안에 들어간다는건 동의하는 부분이고 과연 np문제 4='1+3', 2+2.....을n문제'2+2'=4로 볼수 있냐 이말인거죠 그렇게 된다면 모든 np를 n으로 봐서 알고리즘을 효율적으로 만들수 있겠죠

[@gziop1958]

1이 4개니깐

[@가나다라-s9p7p]

문제가 조금은 이해가 되네요. 진짜 최고에요. 컴공 이학년 정도의 지식수준을 요하네요. 이해하는데에만.

[@BBang-Dabang]

계속해서 양자역학이 생각나네요. 양자컴퓨터를 통해서 여러 해답을 동시에 찾는 다면, NP문제가 P문제화될 것 같아요. 마치 미로의 출구를 찾는 과정이 고전컴퓨터는 1명으로 길을 찾는다면 양자컴퓨터는 n명으로 동시적인 길을 찾는 행위를 통해 출구를 찾는 것같이 말이죠. 비전문가적인 아이디어일 뿐이니 재미로 넘어가주셔요

[@mathlab8437]

좋은 의견 감사합니다^^저도 양자역학에 대해서 공부한 적이 있는데 빵치님처럼 생각해볼수도 있을것 같아요~

[@박제현-u7k]

충분히 일리있는 말이지만 p-np문제는 문제를 변환하는 문제이기때문에 양자컴퓨터가 도입된다해도 모든 문제를 양자컴퓨터가 풀수있는 np문제로 변환한다해도 그 문제가 p문제라는걸 증명하는 문제는 여전히 존재할 뿐더러 모든 문제가 그 np문제로 변환할수 있는가에 대한 문제는 여전히 남아있습니다

[@2119조연우]

부분집합의 총 개수가 왜 2^n-1인지 이해가 안되네요 ㅠㅠ

[@kimjunsik540]

공집합 제외요!

[@SJ-ry6br]

부분집합을 뽑을 수 있는 경우의 수는 각 원소를 뽑거나 안 뽑거나 2가지 케이스가 원소 개수 n개 만큼 곱해지는거니까 2*2*2*...*2 = 2^n 근데 모두 뽑지 않는 케이스는 무의미하므로 제외하면 2^n - 1

[@tipy7155]

이 문제가 np같은데 ㄷㄷ

[@지금부터여러분은숨쉬]

와 그러네 ㄷ

[@cwH-s3j]

뭔 말이노..

[@노승수-g2i]

1을 1/3으로 쓸수 있기 때문에 쉽게 나눠지는 유리수라고 착각하지만 실제로는 결코 파이처럼 소수점 끝이 없는 나눌수없는 무리수이다. 1을 1/3 나눌수 없는 무리수를 나눌수 있는 유리수로 변환하여 나눌수 있을까? 1을 3만큼 키운후 3/3으로 나눈 1로 만든 다음 다시줄인것은 불가능할거다. 1이 3이되서 3/3=1유리수로 만들어지만 1/3만큼 줄일수없는 무리수 원래와같다. 그전상태와 같은 상태는 갈수 없다.

[@민트맛물방울]

유리수는 정수의 비로 나타낼수 있는 수입니다..

[@gsy1838]

P=NP 증명함 N=1일때 P=NP

[@신자-o6m]

@@gsy1838 ㅋㅋㅋㅋㅋㅋ N=1 or N=0 or P=0

[@asdasdgs12]

우주천재 ㄷㄷ

[@D-day_7]

오오...

[@바나나초코파이]

수가 아니고 식의 등호 성립여부는 임의의 변수에대해 성립해야하는 것 아닌가요? 그럼 N=1일때만 성립하므로 항상성립하는 등식이 아니므로 P는 NP가 아니라는 결론이 나옵니다.ㅎ 특히나 집합관계에서는 포함되는 경우도 있고 아닌경우도 있는 방정식 같은 상황이 되면 동치가 아니라 교집합의 형태가 되어야할 것 같은데요

[@gsy1838]

@@바나나초코파이 조크는 그저 조크로 받아들이시죠..ㅎㅎ