기타 업적

계산복잡도

계산에 난이도가 있음은 경험적으로 알고 있다. 예외가 있을 수도 있겠으나 대부분의 경우에 사람들은 덧셈보다 나눗셈을 어려워한다. 그렇다면 나눗셈은 덧셈보다 몇 배나 어려울까? 이를 정량적으로 표현하기란 매우 어려운 일이다.

래빈은 계산의 난이도(즉, 복잡도)를 수학적으로 표현하고 서로 다른 계산 사이의 난이도를 비교하는 모형을 처음으로 제안했다.

앞에서 이미 언급했듯이 시작은 매카시가 낸 수수께끼 같은 문제에서 출발했다. 그 문제는 다음과 같다.

전쟁을 벌이고 있는 두 나라가 있다. 각각 A, B라고 하자. A라는 나라에서는 B라는 나라로 첩자를 보낼 계획이다. 이 첩자는 국경을 넘어서 B라는 나라로 들어갔다가 다시 국경을 넘어 돌아와야 한다. 그런데 되돌아올 때 적군으로 오인을 받아서 아군에 의해 사살될 위험이 있다. 이를 피하려면 뭔가 암호를 사용해야만 한다. 예를 들어 “1932년 6월 20일”을 암호로 정하고, 첩자로 선발된 아군과 국경을 지키는 아군이 이를 숙지하면 된다.

하지만 아직도 문제가 있다. 국경을 지키는 아군들이 부주의하게 떠들다가 암호를 입 밖에 내고 이를 적군의 첩자가 엿들어버리면 암호가 무용지물이 되어 버린다. 자, 그렇다면 어떤 방법을 써야 할까?​2​

래빈은 폰 노이만의 작업에서 영감을 받아서 다음과 같은 해법을 내놓았다. 첩자로 선발된 아군에게는 100자리의 숫자를 알려준다. 당연히 첩자에게만 공개된 암호이다. 그런 후 이 100자리의 숫자를 제곱한다. 그러면 200자리의 숫자가 나오는데, 양쪽에서 50자리씩 잘라내어 가운데 토막 100자리의 숫자를 남긴다. 국경을 지키는 병사들에게는 이 숫자를 알려준다. 이제 첩자로 나갔던 병사가 되돌아올 때 암호인 100자리의 숫자를 제시하면 국경을 지키는 병사는 그것을 제곱한 후에 양쪽에서 50자리씩 버리고 남은 숫자를 자신이 가지고 있는 숫자와 비교한다. 일치하면 암호가 정확한 것이므로 통과시킨다.

만약 국경을 지키는 병사가 실수로 자신이 전달받은 숫자를 발설했고, 이를 적군이 엿듣게 되면 어떻게 될까? 적군은 이 숫자를 암호로 쓸 수는 없다. 왜냐하면 첩자가 가지고 있는 암호는 그 자체로 쓰이는 것이 아니라 제곱한 후에 사용되기 때문이다. 그렇다면 역으로 암호를 알아낼 수는 없을까? 할 수는 있지만 굉장히 어려운 일이다. 결국은 100자리의 숫자를 하나씩 제곱해가면서 찾는 수밖에 없는데 그걸 찾는 동안, 아마도 첩자는 활동을 완료하고 이미 복귀할 터이다.

여기서 래빈은 스스로에게 질문을 던졌다.

계산하기 어렵다는 것은 어떻게 정의할까? 거기서 더 나아가서 어렵다는 것을 증명하려면 어떻게 해야 하나? 이런 질문을 던진 후에 나는 이 문제를 연구하는데 몰두했습니다. 그래서 나온 논문이 <함수 계산의 난이도와 재귀적 집합의 계층>입니다.​13​

비록 그가 계산복잡도를 정량적으로 모델링한 것은 아니지만, 본격적으로 이 분야의 연구를 촉발했다는 점에서 큰 의미가 있다.

소수성 검사

소수prime는 자기 자신과 1 외에는 인수를 가지지 않는 수이다. 소수는 컴퓨터 암호에서 특별한 의미를 가진다. 대표적인 예가 RSA 암호화이다.

RSA 암호화의 핵심은, 두 개의 소수를 곱해서 암호화 키(공개키)를 만드는 데에 있다. 이 키로 암호화된 데이터를 풀기 위해서는 앞서 사용했던 두 개의 소수를 사용해서 만들어 낸 비밀키가 있어야 한다. 따라서 비밀키를 모르는 이가 이 암호를 깨기 위해서는 공개키로부터 두 개의 소수를 유추해낼 수 있어야 하는데 이는 수학적으로 어려운 문제이다.(다시 말하자면 그냥 될 때까지 계속 시도해보는 것과 차이가 없다는 의미이다.)

RSA 암호화를 하려면 소수가 여러 번 필요하다. 그런데 암호화에 사용되는 소수는 매우 커야 하며, 미리 소수들의 집합을 유지하기란 현실적으로 어렵다. 따라서 어떤 수를 선택한 후에 이것이 소수인지를 판별할 필요가 생긴다. 이것이 소수성 검사primality test이다.

밀러와 래빈은 어떤 수가 소수인지 아닌지를 비교적 빠른 시간 내에 판별해내는 알고리듬을 개발했다. 이는 무작위 알고리듬에 기반했다. 즉, 소수인지 여부를 검사하기 위해서 임의의 수를 선정해서 사용했다. 이 검사를 통과하지 못하면 그것은 소수가 아님이 확실하다. 하지만 이 검사를 통과한다고 해서 소수임을 100% 보장하지 못한다. 그래서 또 다른 임의의 수를 선정해서 또 검사를 해야 한다. 여기서 통과하지 못하면 소수가 아님이 확실하지만 통과한다고 해도 역시 소수임을 100% 보장하지 못한다. 단지 시험을 통과하는 횟수가 많아질수록 소수일 가능성이 점점 커진다.

이렇게 무작위로 여러 번 반복하여 시험할 경우에 소수가 아닌 수를 소수로 오인할 확률이 1/(4^n)보다 작음을 래빈은 증명했다.

  1. ​*​
    출처: https://upload.wikimedia.org/wikipedia/commons/d/d9/Michael_O._Rabin_2004.jpg, CC-BY-SA 2.5 Si
  2. ​†​
    출처: https://upload.wikimedia.org/wikipedia/commons/3/35/Scott_Dana_small.jpg, CC BY-SA 2.5 Si
  3. ​‡​
    출처: https://upload.wikimedia.org/wikipedia/commons/4/49/M_O_Rabin.jpg, CC BY-SA 2.0 DE
  4. ​§​
    그는 후에 이스라엘 총리가 되는 벤자민 네타냐후의 삼촌이다
  5. ​¶​
    이스라엘에서는 독립 전쟁이라고 부르지만 통상적으로 제1차 중동전쟁이라고 부른다.
  6. ​#​
    출처: 1976 ACM Turing Award Lectures, Communications of the ACM, Vol.20, No. 9, September 1977.
  7. ​**​
    1969년에 래빈은 Decidability of second-order theories and automata on infinite trees라는 논문을 발표했는데 스콧과 의견을 주고 받았다는 언급을 했다.
  8. ​††​
    고등연구원에는 폰 노이만의 지휘 아래 제작된 전자식 컴퓨터가 있었다. 폰 노이만이 일찍 세상을 떠난 후 고등연구원은 이 컴퓨터를 유지할 비용을 감당하기 싫어했고 결국 이 컴퓨터는 그대로 사장되고 만다. 하지만 이 컴퓨터의 구조는 무료로 다른 대학교와 연구소에 제공되었고 전자식 컴퓨터가 확산되는 데 큰 역할을 했다.
  9. ​‡‡​
    출처: https://upload.wikimedia.org/wikipedia/commons/6/6e/CIMA_mg_8332.jpg, CC SA-2.0 Fr.
  10. ​§§​
    계산할 수 없는 경우가 있음을, 알론조 처치와 앨런 튜링은 각각 독자적 방법을 사용해서 증명했다.
  11. ​¶¶​
    촘스키가 사용한 예는, “무색의 초록색 아이디어가 맹렬히 잠잔다(Colorless green ideas sleep furiously)”이다.
  12. ​##​
    그렇지 않다면 코드가 정상적으로 수행되었는지를 어떻게 검증하겠는가?
  13. ​***​
    의미론의 초기 연구자로는 로버트 플로이드, 토니 호어 등을 들 수 있다. 두 사람은 모두 튜링상을 수상했다.
  14. ​†††​
    현실적으로는 프로그램의 모든 가능한 상태에 대해 이 수식이 수행될 가능성은 없으므로 이것은 partial function이 될 것이다.

참고문헌

  1. 1.
    Scott DS. Logic and programming languages. ACM Turing Award Lectures.:1976. doi:10.1145/1283920.1283932
  2. 2.
    An Interview with Michael Rabin by David Harel. ACM; 2015:35. https://amturing.acm.org/pdf/RabinTuringTranscript.pdf
  3. 3.
    Interview with Data Scott by Gordon Plotkin. ACM; 2020:1. https://amturing.acm.org/interviews/scott_1193622.cfm
  4. 4.
    Rabin MO. Complexity of computations. ACM Turing Award Lectures.:1976. doi:10.1145/1283920.1283931
  5. 5.
    픽오버클리퍼드 A. 인공지능: 100개의 징검이야기. 지식함지; 2020.
  6. 6.
    Rabin MO, Scott D. Finite Automata and Their Decision Problems. IBM J Res &amp; Dev. Published online April 1959:114-125. doi:10.1147/rd.32.0114
  7. 7.
    Entscheidungsproblem. Wikipedia. Accessed August 8, 2022. https://en.wikipedia.org/wiki/Entscheidungsproblem
  8. 8.
    코플랜드 잭. 앨런 튜링: 컴퓨터와 정보 시대의 개척자. 지식함지; 2014.
  9. 9.
    Rabin MO. Probabilistic automata. Information and Control. Published online September 1963:230-245. doi:10.1016/s0019-9958(63)90290-0
  10. 10.
    Büchi JR. On a Decision Method in Restricted Second Order Arithmetic. The Collected Works of J Richard Büchi. Published online 1990:425-435. doi:10.1007/978-1-4613-8928-6_23
  11. 11.
    Fulton III S. John W. Backus (1924 – 2007). Betanews. Accessed August 8, 2022. https://betanews.com/2007/03/20/john-w-backus-1924-2007/
  12. 12.
    Scott D, Strachey C. Toward a Mathematical Semantics for Computer Languages. In: ; 1971.
  13. 13.
    Shasha D, Rabin M. Michael Rabin Interview: February 22 and March 1, 2009. ACM Oral History interviews on –. Published online 2006. doi:10.1145/1141880.1529269

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

1 2 3 4 5