전문가들은 어떻게 보나 — Gasarch 의 세 차례 설문

William Gasarch 는 2002년, 2012년, 2019년 세 차례에 걸쳐 연구자들에게 P 대 NP 가 어느 쪽으로, 언제 풀릴지 물었다. 이 글은 그 결과를 보고서의 수치 그대로 옮기고, 소수 의견과 Knuth 의 견해, 그리고 여론은 증명이 아니라는 단서를 함께 적는다.

세 차례의 설문

증명이 없을 때 남는 것은 전문가들의 짐작이다. 메릴랜드 대학의 William Gasarch 는 그 짐작을 기록으로 남겼다. 그는 이론 전산학 연구자들에게 P 대 NP 가 어느 쪽으로 풀릴지, 언제 풀릴지, 어떤 기법이 쓰일지를 묻고 결과를 학술 소식지 SIGACT News 의 복잡도 이론 칼럼에 실었다.

P 와 NP 는 같은가

세 번째 보고서에 실린 비교표에서 주요 항목을 옮기면 다음과 같다. 백분율은 보고서에 적힌 값이며, Gasarch 는 대략의 값이라고 밝혀 두었다.

읽을 수 있는 것은 세 가지다.

• 대다수가 P ≠ NP 라고 본다. 그 비율은 61%, 83%, 88% 로 늘었다.
• 2002년에는 다섯에 한 명 넘게 의견을 내지 않았다. Gasarch 는 이것이 생각보다 큰 불확실성을 보여 준다고 적었다. 이 무리는 2012년에 거의 사라졌다.
• 2019년에는 모두가 둘 중 하나를 골랐다. 다만 이때는 「예」와 「아니오」를 고르는 설문 도구를 처음 썼고, Gasarch 스스로 색다른 답이 줄어든 까닭이 거기 있을 수 있다고 덧붙였다.

언제 풀릴까

낙관은 한 번 꺾였다가 돌아왔다. Gasarch 는 2019년의 66% 가 놀랍다고 썼다. 2012년 뒤로 문제 해결 쪽의 진전이 거의 없었기 때문이다. 동시에 결코 풀리지 않는다는 답도 가장 많았다.

2002년 응답을 10년 단위로 나눈 표를 보면 2010년대에 풀린다는 사람이 12명, 2020년대가 13명이었다. 앞의 예측은 이미 빗나갔다. 예측이 얼마나 어려운지는 응답자들도 알았다. 2019년에 Peter Shor 는 2050년대라고 답하면서, 아무도 30년 넘게 앞을 내다볼 수는 없으니 그 전에는 아닐 것이라는 뜻일 뿐이라고 했다.

소수 의견

P = NP 라고 답한 사람은 세 번 모두 열에 한 명꼴이었다. Gasarch 는 2002년 보고서에서 그 9명 대부분이 학계에서 존중받는 사람들이었고, 모두 자기 의견이 소수라는 것을 알고 있었으며, 몇몇은 일부러 반대편에 섰다고 말했다고 적었다.

가장 널리 알려진 소수 의견은 Donald Knuth 의 것이다.

• 2002년 설문에서 그는 가장 나쁜 각본을 내다보았다. 누군가 「반대 가설을 가로막는 장애물이 유한 개뿐이므로 P = NP」라는 식으로 증명해서, SAT 를 푸는 다항 시간 알고리즘이 존재한다는 것만 알고 그 복잡도는 끝내 모르게 된다는 것이다.

• 2014년의 문답에서 그는 P = NP 라고 믿게 되었다고 말했다. 그러면서 증명되더라도 쓸모는 없으리라고 덧붙였다.

  Knowledge of the mere existence of an algorithm is completely different from the knowledge of an actual algorithm.

  알고리즘이 그저 존재한다는 것을 아는 것은 실제 알고리즘을 아는 것과 완전히 다르다.

  Donald E. Knuth, 2014

  그래프 이론의 Robertson–Seymour 정리가 그의 본보기다. 다항 시간 알고리즘이 있다는 것은 증명되었지만 그 알고리즘이 무엇인지는 대부분의 경우 알려져 있지 않다.

• 2019년 설문에서도 그는 P 대 NP 가 다항 시간 알고리즘을 아느냐가 아니라 그것이 존재하느냐의 문제일 뿐임을 사람들이 깨닫기 바란다고 적었다.

Knuth 의 견해는 「좋은 알고리즘을 곧 찾을 것」이라는 낙관과는 다르다. 「같다」와 「다르다」 사이에 「같지만 아무도 쓸 수 없다」는 자리가 있다는 지적이다.

여론은 증명이 아니다

이 숫자들을 읽을 때 붙여야 할 단서가 있다.

• Gasarch 자신의 말이다. 첫 보고서에서 그는 이 설문이 문제를 푸는 데도, 언제 풀릴지 아는 데도 우리를 한 걸음도 다가가게 하지 않으며, 이 시대의 주관적 의견에 대한 객관적 기록일 뿐이라고 썼다.
• 표본은 무작위로 뽑은 것이 아니다. 요청을 받고 스스로 답한 사람들이고, 해마다 받은 방법도 달랐다.
• 다수의 직관은 틀린 적이 있다. 2012년 설문이 실린 칼럼의 머리말은 그런 예를 든다. 한때 대부분의 이론가는 NL 과 coNL 이 다르다고, 대화형 증명이 PSPACE 를 담을 리 없다고 믿었다. 둘 다 반대로 증명되었다. 머리말은 이 분야의 직관이 전에도 틀렸고 P 대 NP 에서도 틀릴 수 있다고 맺는다.

그렇다고 다수 의견에 근거가 없는 것은 아니다. Aaronson 은 여러 이유를 든다. 하한을 증명하기는 본디 어려우므로 P ≠ NP 의 증명이 아직 없다는 것은 이상하지 않다. 반면 P = NP 라면 수십 년 동안 쓸 만한 알고리즘의 실마리조차 나오지 않은 것이 수수께끼가 된다. 그리고 수천 개의 NP-완전 문제 가운데 하나만 다항 시간에 풀렸어도 P = NP 였을 텐데 그런 일은 한 번도 없었다. 그러나 이것들은 근거이지 증명이 아니다. 이 문제는 여전히 열려 있다.

출처

• William I. Gasarch, "The P=?NP poll", ACM SIGACT News 33(2), 2002, 34–47. https://www.cs.umd.edu/~gasarch/papers/poll.pdf (응답자 수와 조사 방법, 2.1절의 10년 단위 표, 2.2절의 집계와 소수 의견에 대한 서술, 서론의 단서, Knuth 의 응답)
• William I. Gasarch, "Guest Column: The second P =? NP poll", ACM SIGACT News 43(2), 2012, 53–77. https://www.cs.umd.edu/~gasarch/papers/poll2012.pdf (응답자 152명, 2.1절의 수상자 21명 집계, 칼럼 머리말의 「틀렸던 직관」)
• William I. Gasarch, "Guest Column: The third P =? NP poll", ACM SIGACT News 50(1), 2019, 38–59. https://www.cs.umd.edu/users/gasarch/BLOGPAPERS/pollpaper3.pdf (세 설문의 비교표 2.1·2.2, 조사 방법의 변화와 그 영향에 대한 언급, 3절의 전문가 집계, Shor 와 Knuth 의 응답)
• Donald E. Knuth, "Twenty Questions for Donald Knuth", InformIT, 2014-05-20. https://www.informit.com/articles/article.aspx?p=2213858&seqNum=17 (17번 문답. 본문의 인용문은 여기서 옮김)
• Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (3장 「Beliefs About P =? NP」)