수학의 7대 난제

*1. P vs NP Problem (P 대 NP 문제)

; 이 문제는 밀레니엄 문제들 중에서 유일하게 컴퓨터와 관련된 문제이다. 많은 사람들은 이를 의아하게 여길 것이다. "요새는 수학 연구를 대부분 컴퓨터로 하잖아?"라고 반문할 것이다. 정말 그렇까? 아니다. 실상은 그렇지 않다. 물론 맞는 말이기도 하다. 대부분의 수치 계산은 컴퓨터에 의해서 수행된다. 그러나 수치 계산은 수학의 작은 부분에 불과하며 핵심적인 부분이 아니다.
전자 컴퓨터는 수학에서 나왔지만 - 컴퓨터를 위해서 위해서 필요한 수학의 마지막 단계는 최초의 컴퓨터가 제작되기 수년 전인 1930년대에 완성되었다 - 지금까지 컴퓨터 세계에서 발생한 중요한 - 세상에서 가장 중요하다고 인정할만한 - 수학적 문제는 단 두 개에 불과하다. 그 두 문제는 계산기계라기보다는 개념적 처리과정으로 이해된 컴퓨터와 관련된다. 물론 이런 이해가 실제 계산에 대해서 중요한 함축을 가질 가능성은 열려 있다. 두 문제 중 하나는 헬베르트의 1900년 문제 목록에 들어있다. 그 문제 - 특성한 방정식들은 컴퓨터로 풀 수 없음을 증명하라는 문제 - 는 1970년에 해결되었다.

다른 한 문제는 더 최근에 제기되었다. 그 문제는 컴퓨터가 얼마나 계산과제들을 효율적으로 해결할 수 있는지와 관련된다. 컴퓨터 과학자들은 계산과제들을 두 개의 주요 범위로 분류한다. P형 과제는 컴퓨터를 통해서 효율적으로 해결할 수 있다. E형 과제는 컴퓨터로 완수할려면 100만년 이상이 걸릴 수도 있다. 안타깝게도 공업이나 상업에서 발생하는 주요 계산과제들은 대부분 세번째 문제인 NP형에 속한다.NP형은 P형과 E형의 중간인 것처럼 보인다. 정말 그럴까? NP형 과제가 실은 변형된 P형 과제인 것은 아닐까? 대부분의 전문가들은 NP와 P가 다르다고 믿는다.(즉, NP형 계산과제는 P형 계산과제와 다르다고 믿는거죠). 그러나 30년에 걸친 노력에도 불구하고 NP가 P와 같은지 여부는 증명되지 않았다. 이 문제의 해결은 공업, 상업, 그리고 인터넷을 비롯한 전자통신에 커다란 영향을 끼칠 것이다.




*2. Poincaré Conjecture (푸앵카레 추측)

; 거의 한 세기 전 프랑스 수학자 푸앵카레가 처음 제시한 이 문제는 다음과 같은 간단해 보이는 질문에서 시작된다 : 사과와 도넛을 어떻게 구별할 수 있을까? 정말이지 이 질문은 100만 달러의 상금과는 거리가 먼 질문으로 보인다. 하지만 이 질문은 어렵다. 왜냐하면 푸앵카레가 보다 일반적인 경우들에 적용될 수 있는 수학적 해답을 요구했기 때문이다. 그 요구 때문에, 한 입 먹어보면 알지 않느냐는 자명한 해답들은 제거된다. 푸앵카레 자신이 제시한 해답을 알아보자. 만일 당신이 사과 표면에 고무 밴드를 늘여놓았다면, 당신은 그 밴드를 천천히 움직여서 한 점이 되도록 축소시킬 수 있다. 고무 밴드를 자를 필요도 없고, 표면을 떠날 필요도 없다. 반면에 도넛 둘레를 한 바퀴 감도록 고무 밴드를 늘여놓았다고 해보자. 이 경우에는 고무 밴드나 도넛을 자르지 않는 한, 고무 밴드를 한 점으로 축소시킬 방법이 없다. 축소되는 밴드를 이용한 이 구분법을 사과와 도넛의 5차원 변양태에서도 적용할 수 있을까? 푸앵카레가 묻는 질문이 바로 이것이다. 놀랍게도 아직 아무도 이 질문에 답하지 못했다. 푸앵카레 추측에 따르면, 고무 밴드 발상을 이용해서 4차원 사과를 식별할 수 있다.

이 문제는 현대 수학에서 가장 흥미로은 분양들 중 하나인 위상학의 핵심에 놓여 있다. 위상학은 그 자체로 흥미롭고 때로는 기발한 발상으로 수학적 이성인들을 사로잡을 뿐만 아니라 - 예를 들면 위상학은 도넛과 커프 잔이 심층적이고 그본적인 관점에서는 동일하다고 말한다 - 수학의 여러 분여들과 관계된다. 위상학의 발전은 컴퓨터 칩을 비롯한 전자부품의 설계와 생산, 운송, 뇌 연구, 심지어 영화산업에도 영향을 끼친다.


*3. Navier-Stokes Equation(내비어-스톡스 방정식)

;내비어-스톡스 방정식들은 배의 몸통 주위를 흐르는 물이나 비행기 날개 우이로 흐르는 공기 같은 유체와 기체의 흐름을 기술한다. 그 방정식들은 수학자들이 말하는 이른바 편미분방정식이다. 과학이나 공학을 전공하는 대학생들은 의례적으로 편미분 방정식의 해법을 배운다. 내비어-스톡스 방정식들은 외관상 대학 미적분학 교과서에나오는 편미분방정식 연습 문제와 다르지 않아 보인다. 그러나 외관은 기만일 수 있다. 오늘날까지 그 누구도 내비어-스톡스 방정식의 해의 공식을 찾을 단서조차 발견하지 못했다 - 그런 공식의 존재 여부조차 밝혀지지 않았다.

이 실패에 아랑곳하지 않고 해양공학자들은 효율적인 배를 설계하고, 항공공학자들은 우수한 비행기를 설계한다. 내비어-스톡스 방정식을 푸는(2차방정식 해의 공식과 유사한) 일반 공식은 없지만, 컴퓨터를 이용하여 특정 형태의 방정식들에 대한 근사적인 해를 구하는 것은 가능하기 때문이다. 양-밀스 문제와 마찬가지로 내비어-스톡스 문제 역시 수학이 다른 분야를 따라잡을 것을 요구한다. 이 문제의 경우에는 공학자들이 이미 하고 있는 일을 수학이 따라잡아야 한다.

"따라잡는다"는 표현이 그릇된 인상을 줄지도 모르겠다. 뒤쳐지기 싫어하는 수학자들의 자존심이 관건이라는 인상 말이다. 그런 인상을 가진다면, 과학적 지식이 발전해고는 방식을 오해한 것이다. 수학은 본성상 추상적이기 때문에, 현상을 수학적으로 이해한다는 것은 일반적으로 가장 깊고 확실하게 이해한다는 것이다. 또한 무엇인가를 더 깊게 이해하면, 그것을 더 잘 이용할 수 있다. 질량 간극 가설의 증명이 물리학에 획기적인 발전을 가져올 것과 마찬가지로, 내비어-스톡스 방정식 풀이는 해양 및 항공공학의 발전을 가져올 것이 분명하다.


4. Riemann Hypothesis(리만 가설)

; 이 문제는 1900년 힐베르트가 제시한 문제들 중 미해결로 남아 있는 유일한 문제이다. 어떤 특정한 방정식의 가능한 해들과 관련된 이 기묘한 형태의 문제가 수학의 미해결 문제들 중 가장 중요한 문제라는 것에 전 세계 수학자 대부분이 동의한다.

이 문제는 1859년 독일 수학자 리만에 의해서 처음 제기되었다. 리만은 다음과 같은 오랜 수학적 질문에 대한 답을 추구하고 있었다:소수들이 무엇인가 패턴을 가지고 있을까? 기원전 350년경 유명한 그리스 수학자 유클리드는 소수가 영원히 계속된다는 것을, 즉 무한히 많이 소수가 존재한다는 것을 증명했다. 더 나아가 실제로 소수를 나열해보면, 수가 커질수록 소수가 점점 '엷어져서' 드물게만 나타나는 듯이 보인다. 하지만 소수에 관해서 이 이상의 이야기를 할 수 있을까? 사실상 할 수 있다. 리만 가설이 증명된다면, 소수와 소수의 분포에 관한 우리의 지식이 발전할 것이다. 또한 그 증명은 수학자들의 호기심을 만족시키는 것 이상의 귀결을 가져올 것이다. 그 증명은 소수들의 패턴을 휠씬 넘어선 수학적 귀결들을 가질 뿐 아니라, 물리학과 현대 통신기술에도 응용될 것이다.



*. Hodge Conjecture (호지 추측- 진짜 골때리죠ㅋ)

; 이 문제는 현재 위상학에 결여된 또 하나의 조각이다. 이 일반적인 문제는 어떻게 단순한 대상들로부터 복잡한 수학적 대상을 구성할 수 있는지와 관련된다. 이 문제는 아마도 밀레니엄 문제들 중에서 일반인이 이해하기가 가장 어려운 문제일 것이다. 기반에 있는 직관이 다른 문제들에 의해 덜 분명하거나, 다른 문제들보다 더 난해하기 때문이 아니다. 오히려 일반은이 겸험하게 될 어려움은 호지 추측이 특정한 종류의 추상적 대상들을 분류하기 위해서 수학자들이 사용하는 기법과 관련되기 때문에 발생한다. 호지 추측은 그 분류법의 심층에서 나오며 추상 수준이 높다. 그 추상 수준에 도달하는 유일한 길은 점점 높아지는 추상 수준들을 거쳐 올라가는 길이다.
호지 추측을 향한 길은 20세기 전반기에 수학자들이 복잡한 대상들의 모양을 탐구하는 강력한 방법을 발견하면서 열렸다. 그 방법의 기반에 있는 발상은 주어진 대상의 모양을 단순한 기하학적 벽돌들을 짜맞춤으로서 어느 정도까지 근사시킬 수 있는지를 묻는 것이었다. 그 방법은 매우 유용했고 여러 방식으로 일반화되었다. 수학자들은 그 방버들을 발전히켜 강력한 기법들을 만들어냈다, 결국 많은 다양한 종류의 대상들을 나열한 목록에 도달했다. 하지만 불행하게도 기법들이 일반화 되는 과정에서 기하학적 근원이 흐려졌다, 수학자들은 기하학적 해석이 전혀 없는 대상들도 목록에 포함시켜야 했다. 호지 추측은 중요한 대상들의 집합(투사 대수 다양체projective algebraic varieties라고 불린다)에 대해서는, 호지 회로라고 불리는 조각들이 기하학적 조각들(대수 회로라고 불립니다)의 조합이라고 주장한다.



6. Birch and Swinnerton-Dyer Conjecture(버츠와 스위너톤-다이어 추측)

:이 문제에서 우리는 다시 리만 가설에서와 마찬가지로 일반적이 수학 영역으로 돌아오게 된다. 고대 그리스 시대 이래 수학자들은 다음과 같은 유형의 대수 방정식의 모든 정수해를 기술하는 문제를 놓고 씨름해왔다.
x² + y² = z²
이 특정한 방정식에 대해서는 유클리드가 완벽한 해답을 제시했다 - 즉 모든 해들을 산출하는 공식을 제시했다. 1944년 와일스는 2보다 큰 임의의 지수n에 대해서 방정식
x^n + y^n = z^n
이 0이 아닌 정수해를 가지지 않음을 증명했다.(이 결론이 페르마의 마지막 정리이다). 그러나 더 복잡한 방적식들에 대해서는 정수해가 있는지, 혹은 어떤 정수해가 있는지를 밝혀내기가 매우 어렵다. 버치와 스위너톤-다이어 추측은 그 난해한 방정식들 중 한 유형에 대해서 가능한 해들에 관한 정보를 제시한다.

이 문제는 리만 가설과 관련이 있으며, 이 문제가 해결된다면 소수에 대한 우리의 전반적인 이해에 도움이 될 것이다. 이 문제의 해결이 리만 가설 증명처럼 수학 이외의 영역에도 영향을 미칠지 여부는 불분명하다. 버치와 스위너톤-다이어 추측 증명은 수학자에게만 국한된 관심사로 판명될지도 모른다.

그러나 이 문제를 비롯한 많은 수학 문제가 "실용성이 없다"고 판정하는 것은 어리석은 일이다. 물론 "순수 수학"의 추상적 문제들을 연구하는 수학자드릉ㄴ 대개 어떤 실용적인 귀결에서 동기를 얻기보다는 지적 호기심에서 동기를 얻는다. 그러나 순수 수학에서의 발견이 중요한 실용적 귀결을 같는다는 사실은 역사 속에서 누차 입증되었다.

뿐만 아니라 한 문제를 풀기 위해서 수학자들이 개발한 기법들이 전혀 다른 문제들에 응용될 수 있다는 사실이 종종 입증되었다. 와일스가 페르마의 마지막 정리를 증명한 것이 전형적인 그런 사례이다. 이와 유사하게 버치와 스위너톤-다이어 추측의 증명 역시 다른 용도가 발견될 새로운 발상들을 포함할 것이 거의 확실하다.


7. Yang-Mills and Mass Gap(양-밀스 이론과 질량 간극 가설)

; 수학의 새로운 발전을 위한 계기는 상당 부분 과학 특히 물리학으로부터 주어진다. 예를 들면 수학자 뉴턴과 라이프니츠가 17세기에 미적분학을 발명한 동기는 물리학을 위해서였다. 미적분학은 연속 운동을 수학적으로 엄밀하게 기술하는 방법을 제공함으로써 과학에 혁명을 일으켰다. 뉴턴과 라이프니츠의 방법은 유효했다. 그러나 미적분학의 기반을 이루는 수학이 제대로 완성되기까지는 약 250년이 더 필요했다. 지난 반세기 정도에 걸쳐서 개발된 물리학 이론과 관련해서 유사한 상황이 벌어지고 있다. 이 일곱 번째 밀레니엄 문제는 수학자들에게 물리학을 따라잡을 것을 요구한다.

양-밀스 바정식들은 양자물리학에서 나왔다. 그 방정식들은 지금으로부터 거의 50년 전에 물리학자 양전닝과 로버트 밀스가 중력을 제외한 자연의 힘들을 기술하기 위해서 정식화했다. 그 방정식들은 훌륭한 성과를 거두었다. 방정식으로부터 도출된 예측들은 전 세계 실험실에서 관찰된 입자들을 설명한다. 그러나 실용적으로 효율적임에도 불구하고 양-밀스 이론은 아직 수학적으로 완성되지 않았다. 일곱 번째 밀레니엄 문제가 요구하는 것 중 하나는 , 그 이론을 공리로부터 출발해서 수하적으로 전개하라는 것이다. 요구되는 수학적 이론은 실험실에서 관찰된 여러 조건에 부합해야 할 것이다. 특히 그 이론은 양-밀스 방적식들의 해라고 상정된 것들과 관련된 "질량 간극 가설"을 (수학적으로)입증해야 한다. 대부분의 물리학자들은 이 가설을 받아들여 전자가 질량을 가지는 이유를 설명한다. 질량 간극 가설을 증명할 수 있는지 여부는 양-밀스 이론을 올바르게 수학적으로 전개했는지 여부를 판가름할 수 있는 좋은 시험기준이라고 여겨진다. 그들 역시 전자가 왜 질량을 가지는지 엄밀하게 설명하지 못하고 있다. 다만 그렇가는 것을 관찰했을 뿐이다.

(출처 : '클레이 수학 7대 난제' - 네이버 지식iN)

LEX - 단어 개수 세기

digit    [0-9]
letter    [a-zA-z]
%{
    int count;
%}

%%
    /* match */
{letter}({letter}|{digit})*    count++;
%%

main() {
    yylex();
    printf( "number of identifiers = %d\n", count );
}

LEX - cygwin 에서 컴파일하기

flex 파일명.l

gcc lex.yy.c -lfl

./a.exe

하면 실행됩니다.

LEX - 입력 단어 순서 새기

%{
    int yylineno;
%}

%%
^(.*)\n    printf( "%4d\t%s", ++yylineno, yytext );
%%

int main( int argc, char *argv[]) {
    yyin = fopen( argv[1], "r" );
    yylex();
    fclose( yyin );
}