계산한계해명의 의의

전문가 제언

지혜란 무엇인가라는 문제는 그리스 철학에서의 연구 대상이었고, 절대 지혜의 전형은 수학이고「기하학을 모르는 자는 이 문을 뚫을 수 없다」라는 Platon의 경구로 대표된다. 고대 그리스의 계산은 컴퍼스와 자를 이용한 작도로 수행되고, 계산 가능성을 묻는 3대 작도문제(입방체배적문제, 원적문제, 각의 3등분)는 무리수, 복소수, 삼각함수 등의 개념이나 방정식이나 수학기호, 좌표기하 등의 수법을 낳고, 200년 이상 과학 전반을 선도하였다.

 

그런데 현대의 계산은 계산기로 프로그래밍된 알고리즘으로 수행하고 인간이 기록하여 활용하는 정보를 전부 기본적으로 계산기에서 취급한다. 즉 그리스시대에 구별되었던 절대 지혜와 인간 생활에서의 지혜가 정보처리에 융합되어 서로 가까워지고 있다. 그러면 인간의 지혜는 어디까지 계산기로 대체되고, 지혜와 계산을 융합한 미래의 계산모델이나 계산수법은 어떤 것일까? 이 철학적이면서 현실적인 물음에 수리적으로 도전하는 것이 계산이론이고, 더 자세히 말하면 계산 한계의 해명이다.

 

알고리즘을 설계하여 문제를 해결할 때에는 계산량의 해석이라는 작업이 있다. 알고리즘의 계산량이 예를 들어 )인 것은 계산시간의 증가가 라는 입력 사이즈 n의 다항식함수에 비례하는 형태 이하로 억제된다는 것이고, 이때를 다항식 시간 알고리즘이라 불리고 클래스 P의 문제라고 말한다. 다항식 시간이 아닌 예를 들어 지수시간의 계산량은 문제 사이즈를 증가시키면 폭발적으로 팽창함으로 극력 피하지 않으면 안 된다. 하지만 안타까운 것은 중요문제에서도 다항식시간 알고리즘이 알려지지 않은 것이 많다.

저자

Takeshi TOKUYAMA

자료유형

연구단신

원문언어

일어

기업산업분류

전기·전자

연도

2013

권(호)

96(9)

잡지명

電子情報通信學會誌

과학기술
표준분류

전기·전자

페이지

672~674

분석자

권*하

분석물

• 계산한계 해명의 의의.pdf [296,149 byte]

이미지변환중입니다.