@@ijlijl1ijl1i 공부를 더 해보니 그런것들이 approximation이라는 큰 분야에 부분들임이 보이더군요 푸리에 시리즈, 푸리에 변환 , 확률적관점에서 다항회귀 등 다루기 어려운 세상 관심사를 다루기 쉬운 함수들로 근사화하는 인간의 한계이면서 상식적인 것들의 출발이 보이는 즐거우면서도 해결해보고 싶은 주제입니다
3:07 에 NP문제의 정의가 비결정론 튜링기계를 사용해 ""다항시간"" 내에 답을 구할 수 있는 문제의 집합이라고 나오는데요. 6:26의 예에서 특정부분집합의 합이 0이 되는지의 문제는 다항시간이 아니라 "지수시간"인데 왜 NP문제인 건가요? 혹시 쉽게 설명해주실분 계신가요...
계속해서 양자역학이 생각나네요. 양자컴퓨터를 통해서 여러 해답을 동시에 찾는 다면, NP문제가 P문제화될 것 같아요. 마치 미로의 출구를 찾는 과정이 고전컴퓨터는 1명으로 길을 찾는다면 양자컴퓨터는 n명으로 동시적인 길을 찾는 행위를 통해 출구를 찾는 것같이 말이죠. 비전문가적인 아이디어일 뿐이니 재미로 넘어가주셔요
충분히 일리있는 말이지만 p-np문제는 문제를 변환하는 문제이기때문에 양자컴퓨터가 도입된다해도 모든 문제를 양자컴퓨터가 풀수있는 np문제로 변환한다해도 그 문제가 p문제라는걸 증명하는 문제는 여전히 존재할 뿐더러 모든 문제가 그 np문제로 변환할수 있는가에 대한 문제는 여전히 남아있습니다
1을 1/3으로 쓸수 있기 때문에 쉽게 나눠지는 유리수라고 착각하지만 실제로는 결코 파이처럼 소수점 끝이 없는 나눌수없는 무리수이다. 1을 1/3 나눌수 없는 무리수를 나눌수 있는 유리수로 변환하여 나눌수 있을까? 1을 3만큼 키운후 3/3으로 나눈 1로 만든 다음 다시줄인것은 불가능할거다. 1이 3이되서 3/3=1유리수로 만들어지만 1/3만큼 줄일수없는 무리수 원래와같다. 그전상태와 같은 상태는 갈수 없다.
수가 아니고 식의 등호 성립여부는 임의의 변수에대해 성립해야하는 것 아닌가요? 그럼 N=1일때만 성립하므로 항상성립하는 등식이 아니므로 P는 NP가 아니라는 결론이 나옵니다.ㅎ 특히나 집합관계에서는 포함되는 경우도 있고 아닌경우도 있는 방정식 같은 상황이 되면 동치가 아니라 교집합의 형태가 되어야할 것 같은데요
이 문제를 보면서 머신러닝에서 신경망이 떠올랐어요
단순한 선형결합을 non-linear한 function을 거치는 과정을 수없이 반복하는 게
우리 세상에 풀기 어려운 NP문제를 P문제처럼 단순화해서 컴퓨터가 반복해서 계산해나가는 과정인 것 같은 느낌이 들었습니다
좋은 관점입니다.
@@ijlijl1ijl1i 공부를 더 해보니 그런것들이 approximation이라는 큰 분야에 부분들임이 보이더군요
푸리에 시리즈, 푸리에 변환 , 확률적관점에서 다항회귀 등
다루기 어려운 세상 관심사를 다루기 쉬운 함수들로 근사화하는 인간의 한계이면서 상식적인 것들의 출발이 보이는
즐거우면서도 해결해보고 싶은 주제입니다
NP 알고리즘을 이해할 수 있게되었어요.
이런 유튜버가 진짜 전문유튜버
좋은영상감사합니다.
진짜 너무 좋은 영상입니다 !!!!!!
오오 좋은 영상입니다 감사합니다~
예시를 알기 쉽게 들어준 게 좋다.
아주 좋은 영상입니다. P, NP에 대해, 이해하기 쉽게 풀이한 영상입니다.
오 너무 재밌게 잘 보았습니다.
PNP 문제 .. 연구를 해서 결실만 맺으면 부와 명예를 동시에 가질 수 있는 주제네요 .. ㄷㄷ
구독합니다
주제가 신비해 생각날 때마다 가끔씩 들어옵니다!
혹시 영상에 사용된 배경음악 출처를 알 수 있을까요?
p=np라면 다항시간내에 푸는 알고리즘을 찾는 것이 어려운 문제라 할때 np이고 이또한 p로 바꿀수 있다는 말이므로 찾는것이 쉬워야 하지 않나요?
영상이 너무 유익해요ㅠㅠㅠ 혹시 2:05 부분에서 쿠르트 괴델이 존 폰 노이만에게 편지를 썼다는 정보는 어디서 찾을 수 있을까요???
8:48
솔직히 n이 2면 되거든요
3:07 에 NP문제의 정의가 비결정론 튜링기계를 사용해 ""다항시간"" 내에 답을 구할 수 있는 문제의 집합이라고 나오는데요.
6:26의 예에서 특정부분집합의 합이 0이 되는지의 문제는 다항시간이 아니라 "지수시간"인데 왜 NP문제인 건가요?
혹시 쉽게 설명해주실분 계신가요...
영상에서 설명이 잘못되었습니다. “지수시간” 문제와 “비-다항시간” 문제는 같지 않습니다.
다항시간 < 비-다항시간 < 지수시간
이런 순서로 되어 있으며, P vs NP 문제는 다항시간과 비-다항시간 문제 간의 관계를 묻는 것이지 지수시간의 문제를 묻는게 아니죠.
비결정론적 튜링 기계는 다음 행동이 여러 개거나 없을 수도 있다는데 1개 이상은 틀린 설명 아닌가요?? 물론 이 영상에서 크게 중요해보이진 않습니다.
마스터키를 찾는 여정이군요
문제가 조금은 이해가 되네요. 진짜 최고에요.
컴공 이학년 정도의 지식수준을 요하네요. 이해하는데에만.
문제를 주고 답을구했을때...즉 2+2=4...답을주고 문제를 구했을때...즉 4=1+3, 2+2...그러니깐 2+2=4와 4=1+3, 2+2와 같음을 수학적으로 증명하라...이건가???
그걸 풀수있으면 완전한AI가 생기는거임
같음을 증명하라는게 구체적으로 (너무 성의없는 예시이긴 하지만;;) n문제 '2+2=4'는 np문제 4=1+3,'2+2'....안에 들어간다는건 동의하는 부분이고 과연 np문제 4='1+3', 2+2.....을n문제'2+2'=4로 볼수 있냐 이말인거죠 그렇게 된다면 모든 np를 n으로 봐서 알고리즘을 효율적으로 만들수 있겠죠
1이 4개니깐
수학의 난제는 완전하다~
계속해서 양자역학이 생각나네요.
양자컴퓨터를 통해서 여러 해답을 동시에 찾는 다면, NP문제가 P문제화될 것 같아요.
마치 미로의 출구를 찾는 과정이
고전컴퓨터는 1명으로 길을 찾는다면
양자컴퓨터는 n명으로 동시적인 길을 찾는 행위를 통해 출구를 찾는 것같이 말이죠.
비전문가적인 아이디어일 뿐이니
재미로 넘어가주셔요
좋은 의견 감사합니다^^저도 양자역학에 대해서 공부한 적이 있는데 빵치님처럼 생각해볼수도 있을것 같아요~
충분히 일리있는 말이지만 p-np문제는 문제를 변환하는 문제이기때문에 양자컴퓨터가 도입된다해도 모든 문제를 양자컴퓨터가 풀수있는 np문제로 변환한다해도 그 문제가 p문제라는걸 증명하는 문제는 여전히 존재할 뿐더러 모든 문제가 그 np문제로 변환할수 있는가에 대한 문제는 여전히 남아있습니다
부분집합의 총 개수가 왜 2^n-1인지 이해가 안되네요 ㅠㅠ
공집합 제외요!
부분집합을 뽑을 수 있는 경우의 수는 각 원소를 뽑거나 안 뽑거나 2가지 케이스가 원소 개수 n개 만큼 곱해지는거니까 2*2*2*...*2 = 2^n
근데 모두 뽑지 않는 케이스는 무의미하므로 제외하면 2^n - 1
1을 1/3으로 쓸수 있기 때문에 쉽게 나눠지는
유리수라고 착각하지만 실제로는 결코 파이처럼 소수점 끝이 없는 나눌수없는 무리수이다.
1을 1/3 나눌수 없는 무리수를 나눌수 있는 유리수로 변환하여 나눌수 있을까?
1을 3만큼 키운후 3/3으로 나눈 1로 만든 다음 다시줄인것은 불가능할거다. 1이 3이되서 3/3=1유리수로 만들어지만
1/3만큼 줄일수없는 무리수 원래와같다.
그전상태와 같은 상태는 갈수 없다.
유리수는 정수의 비로 나타낼수 있는 수입니다..
뭔 말이노..
이 문제가 np같은데 ㄷㄷ
와 그러네 ㄷ
P=NP 증명함
N=1일때 P=NP
@@gsy1838 ㅋㅋㅋㅋㅋㅋ N=1 or N=0 or P=0
우주천재 ㄷㄷ
오오...
수가 아니고 식의 등호 성립여부는 임의의 변수에대해 성립해야하는 것 아닌가요?
그럼 N=1일때만 성립하므로 항상성립하는 등식이 아니므로 P는 NP가 아니라는 결론이 나옵니다.ㅎ
특히나 집합관계에서는 포함되는 경우도 있고 아닌경우도 있는 방정식 같은 상황이 되면 동치가 아니라 교집합의 형태가 되어야할 것 같은데요
@@바나나초코파이 조크는 그저 조크로 받아들이시죠..ㅎㅎ