학과문의사항
우선 저는 수학을 모르는 일반 학생입니다.
클레이 수학 연구소에 얽힌 에피소드를 읽다가 흥미가 생겼는데
그만 너무 빠져버려서 주제를 모르고 여기까지 오게 되었습니다.
여러분에게 질책을 들어야 멈추게 될 것 같습니다.
도움주셨으면 합니다.
귀한 시간 뺏었다면 죄송하고요.
소수문제는 전형적인 NP문제로 알고 있습니다.
소수문제에 대한 어떤 알고리즘 공식을 제안하려 합니다.
∞ ∞ ∞
[{2, (2 Σ +1)}- {(2 Σ +1) ( 2 Σ +1)}]
K=1 k=1 k=1
여기서 K는 자연수입니다.
집합 공식인데요,
정확히 설명을 드리겠습니다.
∞
{2, (2 Σ +1)}
K=1
먼저 2를 포함한 홀수전체의 집합입니다.
{2,3,5,7,9,11,13,15,17,..............................}
이 집합 전체에서 홀수 *홀수 즉 홀수와 홀수를 곱한 값을 차례대로 빼나갑니다.
∞ ∞
- {(2 Σ +1) ( 2 Σ +1)}
k=1 k=1
=-{3*3, 3*5, 3*7, 3*9, 3*11..............}
-{5*3, 5*5, 5*7, 5*9, 5*11...............}
-{7*3, 7*5, 7*7, 7*9, 7*11................}
.
.
.
중복되는 2의 배수, 즉 짝수는 애초부터 집합에서 제해버렸고 나머지 홀수의 배수 또한 사라
지고 남는 수는 소수의 집합만 남게 됩니다.
{2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37,.....}
위는 2를 포함한 홀수 전체의 집합입니다.
여기서 홀수와 홀수를 곱한 전체의 집합을 빼버립니다.
-{3*3, 3*5, 3*7, 3*9, 3*11, 3*13, 3*15,....}
-{5*3, 5*5, 5*7, 5*9, 5*11.....}
-{7*3, 7*5, 7*7, 7*9, 7*11.....}
.
.
.
={2,3,5,7,11,13,17,19, 23,29,31,37....}
이 알고리즘을 컴퓨터에 입력시키면 빠른 속도로 소수를 찾아내리라는 생각이 들었습니다.
단순히 집합만을 쏟아내는 것이 아니라 K의 값을 어떤 수로 입력시키느냐에 따라서 원하는
소수또한 자유자재로 찾아낼 수 있으리라는 것이 저의 생각입니다.
이것이 P대 NP 중, P의 한 예가 되지 않을까 아울러 생각해 봤습니다.
다시 한번 귀한 시간 뺏었다면 죄송합니다.
문제 한번 봐주십시오.
클레이 수학 연구소에 얽힌 에피소드를 읽다가 흥미가 생겼는데
그만 너무 빠져버려서 주제를 모르고 여기까지 오게 되었습니다.
여러분에게 질책을 들어야 멈추게 될 것 같습니다.
도움주셨으면 합니다.
귀한 시간 뺏었다면 죄송하고요.
소수문제는 전형적인 NP문제로 알고 있습니다.
소수문제에 대한 어떤 알고리즘 공식을 제안하려 합니다.
∞ ∞ ∞
[{2, (2 Σ +1)}- {(2 Σ +1) ( 2 Σ +1)}]
K=1 k=1 k=1
여기서 K는 자연수입니다.
집합 공식인데요,
정확히 설명을 드리겠습니다.
∞
{2, (2 Σ +1)}
K=1
먼저 2를 포함한 홀수전체의 집합입니다.
{2,3,5,7,9,11,13,15,17,..............................}
이 집합 전체에서 홀수 *홀수 즉 홀수와 홀수를 곱한 값을 차례대로 빼나갑니다.
∞ ∞
- {(2 Σ +1) ( 2 Σ +1)}
k=1 k=1
=-{3*3, 3*5, 3*7, 3*9, 3*11..............}
-{5*3, 5*5, 5*7, 5*9, 5*11...............}
-{7*3, 7*5, 7*7, 7*9, 7*11................}
.
.
.
중복되는 2의 배수, 즉 짝수는 애초부터 집합에서 제해버렸고 나머지 홀수의 배수 또한 사라
지고 남는 수는 소수의 집합만 남게 됩니다.
{2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37,.....}
위는 2를 포함한 홀수 전체의 집합입니다.
여기서 홀수와 홀수를 곱한 전체의 집합을 빼버립니다.
-{3*3, 3*5, 3*7, 3*9, 3*11, 3*13, 3*15,....}
-{5*3, 5*5, 5*7, 5*9, 5*11.....}
-{7*3, 7*5, 7*7, 7*9, 7*11.....}
.
.
.
={2,3,5,7,11,13,17,19, 23,29,31,37....}
이 알고리즘을 컴퓨터에 입력시키면 빠른 속도로 소수를 찾아내리라는 생각이 들었습니다.
단순히 집합만을 쏟아내는 것이 아니라 K의 값을 어떤 수로 입력시키느냐에 따라서 원하는
소수또한 자유자재로 찾아낼 수 있으리라는 것이 저의 생각입니다.
이것이 P대 NP 중, P의 한 예가 되지 않을까 아울러 생각해 봤습니다.
다시 한번 귀한 시간 뺏었다면 죄송합니다.
문제 한번 봐주십시오.
댓글 7
-
상일
2008.01.04 02:01
-
김용승
2008.01.04 07:04
상일님, 좋은 답변 감사합니다. 수학도가 아닌 저는 어렴풋이라도 이해하기 위해 인터넷을 뒤져가며 이해하려고 노력하였습니다. 그 결과물을 적어봅니다.
가령, 47이라는 숫자가 소수인지 아닌지를 판별하기 위해 걸리는 다항식 시간은 (47-1)/2이 아닐까, 이것을 일반화시키면 2를 제외한 홀수는
(n-1)/2라는 값이 얻어지지 않을까 생각해 보았습니다.
∞ ∞ ∞
[{2, (2 Σ +1)}- {(2 Σ +1) ( 2 Σ +1)}]
K=1 k=1 k=1
23번 {2, (2*1)+1, (2*2)+1, ........... (2*23)+1}
-{3*3, 3*5, 3*7, 3*9,.................}
...........
-{47*3,................}
사실 저는 상일님의 글쓴 내용조차 제대로 파악하지 못하고 있습니다. 예전부터 장난이었으니까 하고 마음을 접어야하는데 이유도 없이 미련이 남네요. -
김용승
2008.01.04 07:12
위의 글 엉망으로 남겨서 죄송합니다. 공식 이상하죠? 수정하려해도 수정이 안되네요. 저의 불찰입니다. 사실 저 공식 제대로 알아본다고 해도 맞는 공식인지조차 의심가지만... -
상일
2008.01.04 20:26
다항식 시간이라는 말의 뜻은 입력이 n 비트인 문제에서 알고리듬 수행시간이 n에 관한 다항식이라는 뜻입니다.
숫자 a를 입력할때는 그것을 이진법으로 쓰면 n=log_2(a) 비트가 필요하죠. 그럼 (a-1)/2 만큼 걸린다면 그것은 (2^n-1)/2가 되어 n에 관한 다항식이 아닙니다. -
김용승
2008.01.04 22:49
상일님... 역시 저는 아마츄어인지라 제가 틀렸다는 것만을 어렴풋이 감지할 뿐 상일님의 글을 도통 이해하고 있지 못합니다. P대 NP는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가를 검증하는 문제로, ....컴퓨터를 활용 이론적으로 완벽한 증명을 해내는 것을 뜻한다. 이 한구절의 문장만을 보고 저는 처음 시작했었더랍니다. 그러다가 상일님의 글을 보고 인터넷을 더 뒤진 후, 내가 모르는 세계가 더 있는건가 보다..이렇게 추측하고 있습니다. 온갖 전문용어들이 난무하더군요. 상일님의 글을 비롯해서 이해가 잘 안가더군요.
잡글에 댓글 달아주신거 감사합니다.
마지막으로, 메르센 소수가 있던데 저의 방법은 어떻습니까?
더 큰 소수를 찾아낼 수 있을 것도 같은데....
(주제 넘었다면 죄송합니다.)
-
상일
2008.01.05 07:06
위에 언급하신 "P대 NP는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가를 검증하는 문제"라는 표현은 사실 P대 NP문제에 대한 해설일 뿐 그것이 문제에 대한 정의는 아닙니다.
P대 NP문제는 엄밀한 수학적 용어로 정의되어 있으니 그 정의를 정확하게 아셔야 헛수고를 피할 수 있습니다. -
김용승
2008.01.05 18:46
상일님.. 매번 저의 부족한 글에 답변 달아주신거 감사합니다. 수학 세계의 정밀성에 대해 느끼고 갑니다.
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
143 | 제 8회 삼성전기 1nside Edge 논문대상 공모 | 캠퍼스 | 2012.05.21 | 4682 |
142 | 수학 프로그램 maple 을 어디서 구할 수 있을까요..(수학교사입니다) [1] | 신진아 | 2012.05.18 | 7474 |
141 | 지금 독학학위제 수학사(지금은 폐지)과정과 카이스트 수리과학과 학부생이 배우는 것 파일보고 비교분석부탁드립니다. | 어떤것이 | 2012.05.13 | 5599 |
140 | 2013학년도 포스텍대학원 학생모집 안내(대학원학과설명회 안내) | 포스텍 서울홍보팀 | 2012.05.03 | 5312 |
139 | 원주율 구하기(0 다음에 오는 가장 작은 수로) | metaldouner | 2012.04.22 | 5118 |
138 | 다음 학기 타원곡선론의 시간이 옮겨졌으면 좋겠습니다. | 시크린 | 2012.04.21 | 4728 |
137 | 서울대 융합과학기술대학원 Dynamic Robotic Systems Lab 석박사 과정 모집 안내 | Dyros | 2012.04.13 | 5442 |
136 | 수학과외선생님 구합니다. | 정아 | 2012.03.30 | 5413 |
135 | 2012 Qualcomm IT TOUR 이공계 대학생 미국 본사 방문행사 | 캠퍼스 | 2012.03.28 | 4713 |
134 | 수치해석 함수들을 알고리즘화 하는 작업을 해주실분을 모집합니다. | 이명우 | 2012.03.26 | 5540 |
133 | 2012년 한국군사과학기술학회 종합학술대회 논문모집 안내 | 이민혜 | 2012.03.21 | 4864 |
132 | 여름학기에 해석학1 과목 개설에 대해 문의 드립니다. [1] | 해석학 | 2012.03.14 | 5037 |
131 | 확률과 통계관련 질문 | 박 세준 | 2011.12.18 | 6104 |
130 | 2012년도 KT&G 장학재단 국내대학원 장학생 선발 | thinkgood | 2011.12.15 | 4573 |
129 | 수학과외선생님을 모십니다 | 푸른 | 2011.12.05 | 5169 |
파악하시는 것을 권해드립니다.
어떤 수가 소수인지 판별하는 문제는 NP이지만
NP완전이 아니고 몇년전에 다항식시간이라는
결과가 나왔습니다. 그렇지만 이것이 P=NP나 P!=NP를
뜻하지는 않습니다.
빠른 속도로 소수를 찾아내는 것이 설령 있다고
하더라도 그것이 P=NP를 뜻하는지 의문이 듭니다.