[일반] 제미나이 번역)노리즈키 린타로의 <용의자 X의 헌신> 평론

[Pie,(ratio8552)]

P는 퍼즐러의 P

『용의자 X의 헌신』(히가시노 게이고)에는 헷갈리기 쉬운 서술이 있다. 2000년 5월, 클레이 수학연구소가 각각의 해결에 100만 달러의 상금을 건 현대 수학의 7대 난제, 이른바 '밀레니엄 현상금 문제' 중 하나에 대해 언급한 다음 대목이다.

"PNP 문제라는 건 당연히 알고 있겠지?" 유카와가 뒤에서 말을 걸어왔다.

이시가미는 뒤돌아보았다.

"수학 문제에 대해, 스스로 생각해서 답을 내는 것과 타인에게 들은 답이 맞는지 확인하는 것 중 어느 쪽이 더 간단한가. 혹은 그 어려움의 정도는 어느 정도인가──클레이 수학연구소가 상금을 걸고 낸 문제 중 하나지."

  "역시 대단하군." 유카와는 웃으며 잔을 기울였다.

이시가미의 설명은 지나치게 간략화되어 있어서 독자의 오해를 사기 쉬운 형태가 되어 있다. 애초에 PNP 문제라는 것은 컴퓨터 알고리즘과 계산량에 관한 예상으로, 보통 떠올리는 수학의 증명 문제와는 상당히 성질이 다르기 때문이다.

가능한 한 알기 쉽게 해설해 보겠다(이하의 설명은 나카무라 토루의 『수학 21세기의 7대 난제』, 오타 카즈오·쿠로사와 카오루·와타나베 오사무의 『정보 보안의 과학』의 서술을 참고했다). 다양한 계산 문제 중에서 해답의 후보가 주어졌을 때 그것이 맞다는 것을 비교적 간단히 검증할 수 있는 문제를 NP 문제라고 총칭한다. 예를 들어, 어떤 정수를 소인수분해하는 문제라면, 해답의 후보가 주어졌을 때 원래의 수를 그 후보로 나누어 떨어지는지 확인하면 그것이 정답인지 아닌지는 금방 알 수 있다. 그러나 그 역은 성립하지 않는다. 정수가 어느 정도 이상 큰 수가 되면, 설령 슈퍼컴퓨터의 힘을 빌리더라도 소인수를 찾아내는 것은 쉽지 않기 때문이다(잘 알려져 있듯, 현재 인터넷에서 표준으로 사용되는 RSA 암호의 원리는 이 사실을 이용하고 있다).

한편, 답을 비교적 빠르게(실용적인 컴퓨터의 계산 비용이 타산에 맞는 수준으로) 찾을 수 있는 문제를 총칭하여 P 문제라고 한다. 어떤 경우라도 유효한, 효율적인 해법이 존재하는 유형의 문제라고 해도 좋다. 모든 P 문제는 NP 문제에 포함되므로, PNP 문제(예상)란 "NP 문제 중에는 답을 쉽게 찾을 수 없는 문제가 있다"는 예상을 나타내고 있으며, 현재 대부분의 컴퓨터 과학자는 이 예상이 맞다는 것을 전제로 연구를 진행하고 있다고 한다.

답이 맞는지 아닌지의 검증이 간단하다면, 해답의 후보를 무작위로 남김없이 확인해 보면 반드시 정답에 도달할 수 있을 것이다. 하지만 어느 정도 이상 큰 정수의 소인수분해가 그렇듯, 그러한 이 잡듯 뒤지는 방법은 답을 내기까지 천문학적인 스케일의 계산 시간이 걸려버려서, 현재 실용화된 컴퓨터의 원리로는 앞으로 아무리 성능이 향상되더라도 도저히 감당할 수 없다는 것을 알고 있다(PNP 예상이 맞을 경우). 따라서 P 문제와 NP 문제의 관계를 표로 나타내면,

라는 것이 된다. 괄호 안의 '다항식 시간'과 '지수 시간'이라는 것은 정답에 이르기까지의 계산량(최악의 경우를 가정하여 이 잡듯 뒤지는 총 수순의 수로 나타냄)의 증가 경향을 표현한 것으로, 전자는 현재의 컴퓨터로 현실적으로 처리할 수 있는 수준, 후자는 문제의 크기(이진수로 표기했을 때의 자릿수)가 늘어나면 순식간에 계산량이 천문학적인 숫자로 부풀어 올라 슈퍼컴퓨터로도 처리가 따라갈 수 없게 되어버리는 수준이다. 대략적인 이미지로서, 10의 2제곱과 20의 2제곱, 2의 10제곱과 2의 20제곱의 차이를 비교해 보면 좋다. 문제의 어려움을 상대적인 계산량의 크고 작음으로 비교하고 있는 셈이라, 페르마의 마지막 정리나 리만 가설의 증명이 어렵다고 하는 것과는 전혀 척도가 다른 논의인 것이다.

이 표를 보면 알 수 있듯이, P와 NP의 갈림길은 스스로 생각해서 답을 낼 때의 난이도(계산량의 크기)에 좌우된다. 이시가미의 설명에 있는 것처럼, 문제를 푸는 것과 그 답을 검증하는 것의 난이도를 비교하고 있는 것은 아니다. 서두에서 히가시노의 서술이 오해를 부르기 쉽다고 말한 것은 그 때문이다.

하지만 이 글의 목적이 트집을 잡으려는 것은 아니다. 왜냐하면 아마도 작가는 설명이 부족하다는 것을 알면서도, '범인'과 '탐정'(이시가미와 유카와)의 비대칭적인 관계를 보여주기 위한 수사법으로서 PNP 문제를 언급했을 가능성이 높기 때문이다.

그런 의미에서 흥미로운 것은 앞선 인용문에 이어지는 다음 부분일 것이다.

수학은 보물찾기와 비슷하다고 그(=이시가미·인용자 주)는 생각한다. 먼저 어느 포인트를 공략해야 할지 파악하고, 해답에 도달할 때까지의 발굴 루트를 고안하는 것이다. 그 계획대로 수식을 조립해 나가며 단서를 얻는다. 아무것도 얻지 못하면 루트를 변경해야 한다. 그러한 일을 꾸준하게, 끈기 있게, 그러나 대담하게 행함으로써 누구도 찾지 못했던 보물 즉 정답에 도달할 수 있는 것이다.

그런 비유를 쓰자면, 타인의 해법을 검증한다는 것은 단순히 발굴 루트를 따라가는 것만으로 간단한 일처럼 생각된다. 하지만 실제로는 그렇지 않았다. 잘못된 루트로 나아가 가짜 보물에 도달한 결과에 대해, 그 보물이 가짜라고 증명하는 것은 때론 진짜를 찾는 것보다 어려운 경우가 있다. 그렇기 때문에 PNP 문제 같은 터무니없는 문제가 제시된 것이다.

이 비유는 그렉 이건의 『디아스포라』에 나오는 '진리 광산'의 이미지와 비슷하지만, 이건의 '진리 광산'에는 '잘못된 루트'나 '가짜 보물'은 존재하지 않는다. 오히려 히가시노의 표현은, 앞으로 나아감에 따라 분기되는 루트를 무작위로──꾸준하고 끈기 있게──없애가며, 시행착오 끝에 정답에 이른다는 절차에 가깝다.

이것은 외길의 효율적인 해법이 존재하는 P 문제가 아니라 NP에 속하는 문제의 해법으로, 공략 포인트를 좁혀가는 과정도 언덕 오르기 알고리즘(Hill climbing)이나 분기 한정법(Branch and bound)이라 불리는 해 탐색 알고리즘과 같은 종류의 발상에 기초하고 있다. 이러한 표현이 나오는 것은 PNP 문제에 대한 작가의 상응하는 이해를 보여주는 것이리라. 따라서 여기서는 번거로운 설명을 피하고, 작품 전체에 장치된 미스디렉션(= '가짜 보물')을 암시하는 수사법을 돋보이게 하기 위해 히가시노가 굳이 느슨한 서술 방식을 택했다고 해석해 두기로 한다.

＊

자, NP라는 약호는 Nondeterministic(비결정성) Polynomial(다항식)의 머리글자에서 따온 것이다. '비결정성 알고리즘'이라는 것을 사용하면 '다항식 시간' 내에 해결할 수 있는 문제라는 것이 본래의 정의다.

'비결정성 알고리즘'에서는 계산의 각 단계에서 몇 가지 선택지가 있어도 된다. 시작하고 나서의 순서는 복수의 선택지가 있는 단계 중 하나를 골라 진행하므로 전체적으로는 무수한 가능성이 생겨난다. 그런데 현재 실용화된 컴퓨터는 원리상 각 단계에서 하나의 결과밖에 낼 수 없도록 되어 있어(이를 '순차 처리'라고 한다), '비결정성 알고리즘'에 대응할 수 없다. 순차적인 '결정론적 알고리즘'밖에 쓸 수 없기 때문에, 무수한 가능성을 이 잡듯 뒤지는 작업도 '다항식 시간'에는 들어맞지 않게 된다. 여러 개의 프로세서를 나란히 놓고 일제히 계산하게 하는 '병렬 처리' 방식에도 물리적인 한계가 있다. '비결정성 알고리즘'을 마음껏 구동하려면 양자 컴퓨터의 실용화를 기다려야만 한다.

문과의 언어로 억지로 번역하자면, NP 문제를 푸는 작업은 시나리오 분기형 노벨 게임, 혹은 예전에 유행했던 게임북을 완전 공략하는 것과 같다. 분기하는 스토리 라인을 이 잡듯 뒤져서 모든 엔딩을 클리어하기 위해서는, 순차 처리적인 외길 스토리가 전개되는 소설을 읽는 것에 비해 방대한 시간을 필요로 한다.

대략적인 이미지를 머릿속에 넣었으니, 미스터리 이야기로 돌아가 보자(이하의 문장은 어디까지나 소박한 유추일 뿐, 수학적인 정확성과는 무관하다). 분기하는 루트를 무차별 대입하여 하나씩 소거해 나가는 것. 이것은 일반적인 경찰 소설(주로 집단 수사형)의 해법 패턴과 다름없다. 바꾸어 말하면, 경찰 소설적인 스토리는 NP 문제에 해당한다. 사건의 난이도는 체크해야만 하는 용의자의 총수와 수사에 필요한 리소스의 규모(인력 부족이나 시간적 제약)에 의해 좌우되기 때문이다.

사건의 해결은 종종 형사의 직감이나 요행에 의해 이루어지는데, 이는 수사 루트의 분기를 작가의 개입으로 제한하여 계산량의 폭발적인 증가를 억제하기 위한 편법으로 해석된다. 1990년대 이후 일반화된 프로파일링에 의한 수사 수법은 확률적인 추정을 도입한 해답 탐색 알고리즘의 일종으로 간주할 수 있으며, 복수의 사건이 동시다발적으로 진행되는 모듈형 플롯은 '병렬 처리'에 의한 해법이라고 해도 무방하다.

이에 반해, 명탐정 시스템의 퍼즐러(제한된 용의자 중에서 효율적으로 범인을 특정할 수 있는 유형)는 P 문제에 해당한다. 물론 이 잡듯 샅샅이 뒤지는 소거법을 특기로 하는 명탐정(예를 들어 엘러리 퀸)도 존재하지만, 여기서는 효율적인 해법의 유무에 주목하기로 한다. 명탐정의 추리는 독자 역시 자력으로 도달할 수 있다는 것이 퍼즐러의 전제인 이상, 작중의 수수께끼는 '결정론적 알고리즘'을 통해 '다항식 시간' 내에 풀 수 있는 문제여야만 한다. 그렇지 않은 것은 공정하고 우아한 해결로 간주되지 않는다.

따라서 『용의자 X의 헌신』에서의 P-NP 문제는 이시가미와 유카와(범인-탐정)의 비대칭적인 관계가 아니라, 유카와의 추리와 경찰 수사 사이의 계산량 크기 차이로 귀착된다. 유카와가 사건의 진상에 도달할 수 있었던 것은 그의 두뇌가 경찰보다 우수했기 때문이 아니다. 유카와는 이시가미라는 지인에 관한 특수한 정보를 미리 입수하고 있었기 때문에, 경찰이 처리해야만 하는 방대한 계산량(NP)을 단숨에 축소하여 외길의 해결 루트(P)에 집중할 수 있었던 것이다. 즉 『용의자 X의 헌신』에서의 P-NP 문제는 눈속임에 불과하다.

만약 히가시노 게이고가 NP 문제의 어려움과 정면으로 맞붙는 소설을 썼다면, 21세기 미스터리의 개막을 알1리는 걸작이 되었을지도 모른다. 이는 필자의 제멋대로인 상상이지만, 가령 이 소설의 탐정역이 아마추어 명탐정인 유카와가 아니라 경찰 조직의 일원인 가가 교이치로였다면, 같은 도서 미스터리(倒叙 미스터리, 범인이 먼저 밝혀지는 형태)라도 해결 절차는 훨씬 더 NP적인 양상을 띠지 않았을까.

하지만 머지않아 본격 미스터리의 '수수께끼와 그 논리적 해결'이라는 회로는, 세계의 데이터베이스화, 즉 계산 가능 영역의 급속한 확대에 따라 P에서 NP로의 이행을 강요받게 될 것임에 틀림없다(P-NP 문제가 해결되는 것과는 어느 쪽이 먼저일까?). 실제로 그러한 경향은 어떤 종류의 서술 트릭 작품에서 서서히 표면화되기 시작하고 있다. 요즈음 독자들의 흥미는 스스로 생각하여 수수께끼를 푸는(답을 내는) 것보다, 갑자기 제시되는 '진상'(해답의 후보)이 주어진 스토리와 정합하는지를 검증하는 쪽으로 향하고 있기 때문이다(주).

NP 영역으로 무게 중심을 옮긴 '수수께끼와 그 논리적 해결'이 기존의 본격 미스터리와 같은 것일지 어떨지는 알 수 없다(스타니스와프 렘의 확률론적 미스터리 『건초열』이 수수께끼 풀이 애호가들의 열기를 완전히 식혀버리는 것처럼 말이다). 하지만 콜린 덱스터의 모스 경감과 같은 '경관=명탐정'의 존재를 잊을 수는 없을 것이다. 수사 소설에서 '비결정론적 알고리즘'의 출현을 예상케 하는 모스의 시행착오……. 참고로 카가미 사부로는 「EQ」 81년 5월호에 게재된 고하라 히로시, 수토 야스오와의 정담 「1980년도 번역 미스터리를 말하다」에서 덱스터의 작품을 언급하며 다음과 같은 흥미로운 지적을 한 바 있다.

카가미 : 트릭에 대해 말하자면── 묘수풀이 중에 '발양론(發陽論)'이라는 것이 있습니다. 프로가 아니면 풀 수 없을 만큼 대단한 바둑 묘수풀이죠. 왜 아마추어는 풀 수 없는가 하면── 평범한 묘수풀이의 형태를 띠고 있지 않기 때문입니다. 푸는 사람에게 묘수풀이를 만들어내는 힘을 요구합니다. 묘수풀이에서 돌을 하나 빼버리면── 이건 바둑을 아는 분이라면 잘 아시겠지만, 정말 기하급수적으로 어려워집니다. 그와 비슷하게, 좀 더 서툰 짓을 덱스터는 하고 있어요. 퍼즐 소설 애호가에게는 확실히 그 편이 더 재미있을지도 모릅니다. 하지만 제 입장에서는 그것이 어쨌든 돌을 빼는 작업일 뿐이지 않은가 하는 느낌이 듭니다. 그로 인해 퍼즐의 난이도가 올라가죠. 그러니까, 덱스터 식이라도 좋다고 한다면 앞으로 퍼즐 소설의 미래는 밝습니다.

(주) 아비코 타케마루가 주장하듯, 서술 트릭 작품의 해법은 의도적으로 생략되었을 가능성이 있는 속성(조건) 기술의 다양한 조합을 무차별 대입하듯 샅샅이 적용해 보며 최적의 패턴을 찾아내는 것이다. 이 조합은 무수히 존재하므로, 작가가 제시하는 '진상'이 스토리와 정합적이라 하더라도 그 이외의 더 복잡한 해답이 존재하지 않는다고 단언할 수는 없다.

[익명(qczbkn9ehcm9)]

[Lain(pk0102)]