학과문의사항

우선 저는 수학을 모르는 일반 학생입니다.

클레이 수학 연구소에 얽힌 에피소드를 읽다가 흥미가 생겼는데

그만 너무 빠져버려서 주제를 모르고 여기까지 오게 되었습니다.

여러분에게 질책을 들어야 멈추게 될 것 같습니다.

도움주셨으면 합니다.

귀한 시간 뺏었다면 죄송하고요.


소수문제는 전형적인 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의 한 예가 되지 않을까 아울러 생각해 봤습니다.


다시 한번 귀한 시간 뺏었다면 죄송합니다.

문제 한번 봐주십시오.




태그 :
조회 수 :
16597
추천 수 :
292 / 0
등록일 :
2008.01.04
00:15:01 (*.116.79.122)
엮인글 :
http://mathsci.kaist.ac.kr/ko/xe/qanda/1696/faf/trackback
게시글 주소 :
http://mathsci.kaist.ac.kr/ko/xe/1696

상일

2008.01.04
02:01:13
(*.248.27.135)
P와 NP 그리고 NP완전 의 정의를 정확하게
파악하시는 것을 권해드립니다.

어떤 수가 소수인지 판별하는 문제는 NP이지만
NP완전이 아니고 몇년전에 다항식시간이라는
결과가 나왔습니다. 그렇지만 이것이 P=NP나 P!=NP를
뜻하지는 않습니다.
빠른 속도로 소수를 찾아내는 것이 설령 있다고
하더라도 그것이 P=NP를 뜻하는지 의문이 듭니다.

김용승

2008.01.04
07:04:02
(*.247.97.60)
상일님, 좋은 답변 감사합니다. 수학도가 아닌 저는 어렴풋이라도 이해하기 위해 인터넷을 뒤져가며 이해하려고 노력하였습니다. 그 결과물을 적어봅니다.

가령, 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:58
(*.247.97.60)
위의 글 엉망으로 남겨서 죄송합니다. 공식 이상하죠? 수정하려해도 수정이 안되네요. 저의 불찰입니다. 사실 저 공식 제대로 알아본다고 해도 맞는 공식인지조차 의심가지만...

상일

2008.01.04
20:26:11
(*.248.27.135)
다항식 시간이라는 말의 뜻은 입력이 n 비트인 문제에서 알고리듬 수행시간이 n에 관한 다항식이라는 뜻입니다.
숫자 a를 입력할때는 그것을 이진법으로 쓰면 n=log_2(a) 비트가 필요하죠. 그럼 (a-1)/2 만큼 걸린다면 그것은 (2^n-1)/2가 되어 n에 관한 다항식이 아닙니다.

김용승

2008.01.04
22:49:56
(*.247.98.4)
상일님... 역시 저는 아마츄어인지라 제가 틀렸다는 것만을 어렴풋이 감지할 뿐 상일님의 글을 도통 이해하고 있지 못합니다. P대 NP는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가를 검증하는 문제로, ....컴퓨터를 활용 이론적으로 완벽한 증명을 해내는 것을 뜻한다. 이 한구절의 문장만을 보고 저는 처음 시작했었더랍니다. 그러다가 상일님의 글을 보고 인터넷을 더 뒤진 후, 내가 모르는 세계가 더 있는건가 보다..이렇게 추측하고 있습니다. 온갖 전문용어들이 난무하더군요. 상일님의 글을 비롯해서 이해가 잘 안가더군요.

잡글에 댓글 달아주신거 감사합니다.
마지막으로, 메르센 소수가 있던데 저의 방법은 어떻습니까?
더 큰 소수를 찾아낼 수 있을 것도 같은데....
(주제 넘었다면 죄송합니다.)






상일

2008.01.05
07:06:18
(*.248.27.135)
위에 언급하신 "P대 NP는 컴퓨터 알고리즘과 관련된 분야로 수학의 귀납법 풀이는 가능하나 연역적 풀이도 가능한가를 검증하는 문제"라는 표현은 사실 P대 NP문제에 대한 해설일 뿐 그것이 문제에 대한 정의는 아닙니다.
P대 NP문제는 엄밀한 수학적 용어로 정의되어 있으니 그 정의를 정확하게 아셔야 헛수고를 피할 수 있습니다.

김용승

2008.01.05
18:46:22
(*.247.94.111)
상일님.. 매번 저의 부족한 글에 답변 달아주신거 감사합니다. 수학 세계의 정밀성에 대해 느끼고 갑니다.
List of Articles
번호 제목 글쓴이 날짜 조회 수
37 MAS650 stochastic DE 과목은 언제 열립니까? 주강현 2008-06-09 14604
36 Msc Mathematics (coursework) [3] Shujian 2008-05-14 15575
35 How does undergraduate credit accumulation exam work? [1] Liu Ling 2008-04-11 16853
34 질문입니다. 임성준 2008-04-06 14952
33 과목개설 건의있습니다. [6] 이대근 2008-03-26 16338
32 학과에 대한 건의사항은 어디에 연락하면 되나요? [1] 이병찬403 2008-03-25 16062
31 질문이 있는데요... 자유게시판을 못 찾아서 또 여기에 질문합니다... [1] 임현일 2008-03-20 15996
30 개설교과목 홈페이지 관련 문의입니다. [1] 김민규376 2008-02-20 16541
29 과목인정에 대해서 질문있습니다. [1] 강형석 2008-02-11 15721
28 미분기하학 과목은 봄학기에는 개설이 안되나요? [1] 김정한 2008-02-11 15921
27 선형대수학개론 학점인정시험 담당 교수님이 어느분이신지 알수있나요? 천유상 2008-02-05 16231
26 질문있습니다. [1] 남태규 2008-01-20 16319
25 재수강 학점 상한선 [1] 최가영 2008-01-05 21929
» 소수문제와 P대 NP에 대한 짧은 아이디어 [7] 김용승 2008-01-04 16597
23 산경동 컴퓨터실 프로그램 설치 관련 [2] 이창환 2007-12-16 16558