기타 업적

버먼-하트마니스 추측

1977년에 하트마니스는 제자였던 버먼Berman과 함께 구조적 복잡도 이론structural complexity theory와 관련된 한 가지 추측을 발표한다. 이는 NP-완전과 관련된 것인데, 모든 NP-완전 문제들은 다항 시간 내에 동형isomorphic을 찾을 수 있을 것이라고 추측했다. 수학적으로 동형isomorphic이라는 것은 구조적으로 동일함을 의미한다. 만약, 이 추측이 증명된다면 NP-완전 문제 중 한 개만 답을 구하면 다른 문제들의 답을 다항 시간 내에 구할 수 있음을 증명하는 셈이다.

컴파일러

스턴즈는 제너럴일렉트릭 연구소에서 일하면서 동료들과 함께 컴파일러에 관한 책을 썼다. 수학 전공자였던 그는 늦게 컴퓨터 프로그래밍을 접했다.

제너럴일렉트릭에 입사할 때까지 나는 컴퓨터를 본 적이 없었습니다. 사실은 입사했을 때도 그곳에는 컴퓨터가 없었습니다. 그러다가 곧 시분할 시스템이 들어왔고 나는 베이직으로 프로그램을 짜 보았습니다…. 얼마 안 가서 시분할 시스템에 포트란이 추가되었습니다…. 시간이 지나자 알골 컴파일러가 개발되었습니다…​5​

당시 제너럴일렉트릭은 컴퓨터 사업에 적극적이었다. 그리고 당시는 context-free 언어가 뜨거운 관심을 받고 있었다. Context-free 언어를 위한 컴파일러는 계산 복잡도가 높았고 스턴즈의 관심을 끌었다. 그는 동료들과 함께 LL(k) 파싱 방법을 개발했고 속성 문법attributed grammar에도 관심을 가졌다.

파워 지표

여기서 파워는 ‘힘’을 의미하는 것이 아니라, 수학에서 쓰는 ‘지수’ 혹은 ‘거듭제곱’을 말한다. 파워 지표power index란, 어떤 문제의 계산 복잡도가 기하급수적exponential할 때 그 정도가 얼마나 되는지를 말한다.

예를 들어 n^2의 복잡도를 가지는 문제가 있는가 하면 n^3의 복잡도를 가지는 문제가 있다. 이 경우 둘 다 실행시간이 기하급수적으로 증가하기는 하지만 파워 지표가 다르기 때문에 증가 속도에는 차이가 있다.

스턴즈는 뉴욕 주립 대학교에서 제자인 헌트Hunt와 함께 파워 지표에 대해 연구했다. 이들은 리덕션reduction을 써서 문제가 다른 형태로 바꿀 때 파워 지표가 어떻게 변하는지 밝혀냈다.​5​

관련 연구들

‘계산 복잡도’는 오늘날 컴퓨터 과학의 가장 큰 화두인 P = NP 문제를 도출시키는 데 직접적인 영향을 끼쳤다. NP 문제를 처음 공론화시켰던 스티븐 쿡은 하버드 대학교 대학원생 시절에 하트마니스의 특별 강의를 통해 ‘계산 복잡도’를 알게 되었다.

흥미롭게도 1965년에 두 명의 연구자가 ‘계산 복잡도’와 관련된 논문을 발표했다. 한 명은 하버드 대학교 수학과 박사과정에 있던 앨런 콥햄Alan Cobham이었고 다른 한 명은 미국 국립표준원에서 일하던 잭 에드먼즈Jack Edmonds였다. 두 사람은 다항 복잡도polynomial complexity라는 개념을 제시했다. 앨런 콥햄은 같은 대학원의 후배였던 스티븐 쿡에게 영향을 주었고, 잭 에드먼즈와 공동 연구를 했던 리처드 카프는 후에 ‘NP-완전’ 개념을 정리했다.

하트마니스와 스턴즈가 ‘계산 복잡도’에 관한 논문을 작성하던 시기에, MIT에서는 마뉴엘 블럼Manuel Blum이 같은 주제로 박사 학위를 준비하고 있었다. 당시에 하트마니스도 그 사실을 알고 있었다.

MIT에서 마뉴엘 블럼이 계산 복잡도에 관한 박사 논문을 준비하고 있었습니다. 그의 방법은 추상적 혹은 공리적 계산 복잡도였습니다. 우리 것은 구체적 복잡도 이론concrete complexity theory이라고 불렸죠. 근본적으로 우리 것은 공리를 통해 만들어지지 않았고 대신에 기계가 잡아먹는 자원의 양을 측정하는 방식이었습니다. 기본적으로 우리는 튜링 기계를 기본 모형으로 사용했고 그 기계가 사용하는 자원의 양을 따졌습니다.​10​

  1. ​*​
    출처: Wikipedia SA-BY-3.0
  2. ​†​
    출처: cis.cornell.edu
  3. ​‡​
    다트머스 대학교 수학과 교수였던 그는, 베이직(BASIC) 언어를 개발하기도 했다.

참고문헌

  1. 1.
    Hartmanis J. Turing award lecture: On computational complexity and the nature of computer science. ACM Turing Award Lectures.:1993. doi:10.1145/1283920.1283949
  2. 2.
    Stearns RE. Turing award lecture: It’s time to reconsider time. ACM Turing Award Lectures.:1993. doi:10.1145/1283920.1283950
  3. 3.
    A. M. Turing Award Oral History Interview with Juris Hartmanis by David Gries. ACM; 2018:1-24.
  4. 4.
    von Neumann J, Morgenstern O. Theory of Games and Economic Behavior. Princeton University Press; 2007.
  5. 5.
    A. M. Turing Award Oral History Interview with Richard (“Dick”) Edwin Stearns by Dan Rosenkrantz. ACM; 2017:1-26.
  6. 6.
    Hartmanis J, Stearns RE. On the computational complexity of algorithms. Trans Amer Math Soc. Published online 1965:285-306. doi:10.1090/s0002-9947-1965-0170805-7
  7. 7.
    Juris Hartmanis. A.M. Turing Award Laureate. Accessed November 5, 2023. https://amturing.acm.org/award_winners/hartmanis_1059260.cfm
  8. 8.
    Rabin MO. Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets. Hebrew University; 1960:1-23.
  9. 9.
    마이클 래빈 / 데이나 스콧 – Page 5 of 5. 지식함지. Accessed November 5, 2023. https://knowledgebasin.com/archives/persons/%eb%a7%88%ec%9d%b4%ed%81%b4-%eb%9e%98%eb%b9%88-%eb%8d%b0%ec%9d%b4%eb%82%98-%ec%8a%a4%ec%bd%a7/5
  10. 10.
    Oral History: Juris Hartmanis. IEEE History Center; 1991:1.

(c) 이재범, 2024
이 콘텐츠는 대한민국 저작권법의 보호를 받습니다. 작성된 모든 내용의 권리는 저자에게 있으며, 저자의 동의 없는 사용은 금합니다. 본 콘텐츠의 일부 혹은 전체 내용을 무단으로 전재/복제/배포하거나 2차적 저작물로 재편집하는 경우, 법적 책임을 지게 됩니다.

1 2 3 4