컴퓨터과학 전공자라면 대학에서 이런 결론을 배웠을 가능성이 크다. NP-하드 문제는 이론적으로는 풀 수 있지만 실제로는 계산 비용이 감당할 수 없을 만큼 커지며, 좋은 알고리즘이 존재하지 않는다는 것이 사실상 증명되어 있다는 것이다. 한 개발자는 자신의 지도교수가 마지막 강의를 "흥미로운 문제의 거의 전부는 결정 불가능하고, 남은 것들의 거의 전부는 NP-하드다. 컴퓨터과학이라는 기획에 이것이 마지막 못을 박는다"는 비장한 말로 끝맺었다고 회고한다. 이런 극적인 프레이밍이 아니더라도, 많은 사람이 비슷한 인상을 안고 학교를 떠난다. 그리고 온라인 토론에서도 "그건 NP-하드라서 안 된다"는 식의 단정이 끊임없이 되풀이된다.
이 글의 핵심 주장은 그 이론이 틀렸다는 것이 아니라, 실무에서는 그 이론이 종종 무의미하다는 것이다. NP-하드라는 판정은 어떤 알고리즘이든 최악의 입력에서는 폭발적으로 느려진다는 뜻이지, 우리가 실제로 마주치는 입력에서 느리다는 뜻이 아니다. 99.9%의 입력에서 빠른 답을 얻거나, 현실적으로 의미 있는 입력 전체에서 빠른 답을 얻는 것을 이론은 전혀 배제하지 않는다. "이론상 이론과 실무는 차이가 없지만, 실무상으로는 차이가 있다"는 오래된 농담이 여기에 그대로 들어맞는다.
최악의 경우는 대개 오지 않는다
글쓴이는 패키지 설치나 타입 검사 같은 작업을 예로 든다. 이런 작업이 느려질 수 있다는 것은 분명하지만, 자신의 경력 전체에서 이론이 경고하는 천문학적 규모의 폭발을 실제로 목격한 적은 없다고 말한다. 이것이 핵심이다. 계산 복잡도 이론이 그리는 최악의 시나리오는 특정한 병리적 입력에서만 발생하며, 실제 소프트웨어가 다루는 데이터는 그런 극단으로 잘 가지 않는다. 최악의 경우가 존재한다는 사실과, 그 경우를 실제로 밟게 된다는 사실은 전혀 다른 이야기다.
최적화 문제로 넘어가면 이야기는 더 흥미로워진다. 흔히 최적화 문제는 휴리스틱으로 대충 풀어야 한다고 여겨지지만, 최적성을 포기해야만 하는 것은 아니다. 합리적인 시간 안에 증명 가능한 최적해를 찾아내는 도구들이 이미 존재하기 때문이다. 여기에는 어떤 마법도, 양자 컴퓨터도 없다. 그저 더 깊이 고민해 더 나은 알고리즘을 만들어낸 결과일 뿐이다.
알고리즘이 하드웨어를 앞질렀다
주목할 만한 대목은 지난 수십 년간 알고리즘의 개선 속도가 하드웨어 발전 속도를 앞질렀다는 점이다. 글이 인용한 논문에 따르면 1991년부터 2015년 사이에 4,500억 배에 달하는 속도 향상이 있었다. 무어의 법칙에 따른 하드웨어 성능 향상만으로는 설명되지 않는 규모이며, 상당 부분이 순수하게 알고리즘 자체의 진보에서 나왔다는 의미다. "불가능하다"는 이론적 판정 아래에서 실무자들은 조용히 문제를 계속 정복해 온 셈이다.
NP-하드 문제의 원형이라 할 수 있는 충족 가능성 문제(SAT)조차 오늘날 대규모로 일상적으로 풀린다. 글에 따르면 아마존은 하루에 10억 건의 SMT 문제를 처리하고 있는데, SMT는 SAT보다 한층 더 어려운 형태다. SAT 알고리즘이 워낙 좋아진 나머지 이제 SAT를 푸는 부분은 전체 과정에서 오히려 쉬운 축으로 여겨진다는 것이다. 교과서가 난공불락의 상징으로 제시하던 문제가 현업에서는 인프라의 일부로 자연스럽게 녹아 있는 것이다.
실무자가 가져갈 교훈
그렇다면 정말로 최악의 경우에 맞닥뜨리면 어떻게 하나. 우주의 열죽음까지 기다릴 필요는 없다는 것이 글쓴이의 답이다. HTTP 요청도 가끔은 응답이 돌아오지 않는다. 그럴 때 우리는 타임아웃을 걸고 오류 메시지를 띄우는 익숙한 대응을 한다. NP-하드 문제 역시 마찬가지로, 예외적으로 느려지는 입력에 대해서는 시간 제한을 두고 실패를 우아하게 처리하면 된다. 최악의 경우를 시스템 설계의 한 예외 상황으로 다루면 될 뿐, 문제 전체를 포기할 이유가 되지는 않는다.
물론 이 주장에는 한계도 분명하다. 실무 입력이 병리적 최악의 경우로 가지 않는다는 것은 경험적 관찰이지 보장이 아니며, 적대적 입력이 들어올 수 있는 영역에서는 최악의 경우가 곧 공격 표면이 되기도 한다. 인용된 4,500억 배 같은 수치도 특정 문제군에서의 누적 개선을 합산한 것이어서 모든 NP-하드 문제에 그대로 적용되지는 않는다. 그럼에도 이 글이 던지는 실용적 메시지는 유효하다. "NP-하드니까 안 된다"는 반사적 단정에 멈추기보다, 내가 실제로 다룰 입력의 분포를 살피고 최적화 솔버 같은 성숙한 도구를 먼저 시도해 보라는 것이다. 이론적 불가능성과 실무적 처리 가능성은 별개의 질문이며, 둘을 구분하는 것만으로도 접근할 수 있는 문제의 범위가 크게 넓어진다.