Stephen Wolfram이 또다시 거대한 주제를 들고 나왔습니다. 이번엔 컴퓨터 과학의 성배(Holy Grail)라 불리는 P vs NP 문제입니다.

솔직히 제목만 보고 “아, 또 Wolfram 형님이 본인 스타일대로 모든 걸 재정의하려나 보다”라고 생각했습니다. 2026년 1월에 올라온 이 긴 글은, 그가 오랫동안 주장해온 ‘Ruliology(규칙학)‘의 관점에서 계산 복잡도(Computational Complexity)를 실증적으로 뜯어본 결과물입니다.

결론부터 말하자면, 이 글은 P vs NP를 수학적으로 증명하거나 해결하지 않습니다. 하지만 엔지니어 관점에서 보면 “극한으로 최적화된 작은 프로그램들이 실제로 어떻게 동작하는가?” 에 대한 매우 흥미로운 데이터셋을 제공합니다.

오늘은 이 글이 던지는 화두와, Hacker News에서 오간 논쟁, 그리고 제 개인적인 기술적 견해를 정리해 보겠습니다.

이론이 아니라 ‘실측’으로 접근하는 CS

보통 우리는 알고리즘 복잡도를 논할 때 Big-O 표기법을 쓰며 $N$이 무한대로 갈 때를 상정합니다. 하지만 Wolfram은 반대로 접근합니다.

“가능한 모든 작은 튜링 머신(Turing Machine)을 다 돌려보자.”

그는 상태(state)가 2개, 3개인 튜링 머신들을 전수 조사(enumerate)했습니다. 입력값에 대해 이 머신들이 얼마나 빨리 답을 내놓는지, 혹은 영원히 멈추지 않는지(Halting Problem)를 실측(Empirical) 한 것입니다.

이 접근 방식이 꽤 신선한 이유는, 우리가 흔히 작성하는 코드가 아니라 “우주에 존재할 수 있는 가장 작은 프로그램들의 전수 조사” 라는 점 때문입니다. 이를 통해 특정 함수를 계산하는 데 필요한 ‘절대적인 최소 시간’과 ‘최소 코드 크기’를 물리적으로 매핑하려고 시도합니다.

복잡도의 ‘간극(Gap)’ 발견

글에서 가장 흥미로웠던 부분은 Runtime Profile 분석입니다. 수백만 개의 튜링 머신을 돌려봤더니, 실행 시간의 증가 패턴이 연속적이지 않다는 겁니다.

• Linear ($O(n)$): 아주 많음.
• Quadratic ($O(n^2)$): 꽤 있음.
• Exponential ($2^n$): 많음.

그런데 그 사이, 예를 들어 $n \log n$이나 $n^{1.5}$ 같은 복잡도를 가진 머신은 작은 사이즈($s=3$)에서는 거의 발견되지 않았습니다. Wolfram은 이를 두고 “중간 단계의 성장(Intermediate Growth)은 매우 드물다”고 지적합니다.

이것이 시사하는 바는 큽니다. 우리가 현업에서 마주하는 복잡한 시스템도, 기저(low-level)로 내려가면 결국 몇 가지 기본적인 복잡도 클래스로 ‘양자화(Quantized)‘되어 귀결될 수 있다는 직관을 줍니다. 마치 물리적 라우팅 비용처럼, 계산 비용도 특정 임계값을 넘어가면 계단식으로 뛴다는 것이죠.

‘Isolate’ 머신과 최적화의 한계

Wolfram은 특정 함수를 계산하는 가장 빠른 머신을 Isolate 라고 부릅니다. 이는 엔지니어링으로 치면, 더 이상 줄일 수 없는 ‘Hand-optimized Assembly’의 극한입니다.

재미있는 건, 어떤 함수들은 우리가 생각하는 것보다 훨씬 복잡한 방식으로만 계산 가능하다는 점입니다. 그는 이를 Computational Irreducibility(계산적 환원 불가능성) 라고 부릅니다. 즉, “이 프로그램이 무슨 일을 할지 미리 알 수 있는 지름길(shortcut)은 없다. 그냥 돌려봐야 안다”는 것입니다.

이 지점에서 P vs NP 문제와 연결됩니다. 만약 모든 계산이 ‘환원 불가능’하다면, 우리는 영원히 다항 시간(Polynomial time) 내에 검증 가능한 해를 찾지 못할 수도 있다는 암시를 줍니다.

Hacker News의 반응: “흥미롭지만 제목 낚시 아냐?”

Hacker News의 반응은 예상대로 엇갈렸습니다. 저도 동의하는 베스트 댓글 중 하나는 다음과 같습니다.

“이건 P vs NP 문제의 해결이라기보다는, 제한된 프로그램 크기 예산(budget) 내에서 절대적인 속도 제한을 매핑한 것이다. 비록 P vs NP를 직접 건드리진 못해도, 실제 규칙 공간(Rule Space)에서 난이도가 어떻게 분포하는지 보여주는 훌륭한 자료다.”

반면, 비판적인 시각도 만만치 않습니다.

“제목은 완전 낚시(Clickbait)다. 다항식(Polynomial)과 관련된 문장을 다 빼도 글의 정보량은 변하지 않는다.”

솔직히 저도 이 의견에 한 표 던집니다. Wolfram은 항상 본인의 이론(Ruliad, Cellular Automata)을 설명하기 위해 기존 학계의 난제들을 끌어오는 경향이 있습니다. 이 글도 P vs NP를 푼다기보다는, 본인의 ‘Ruliology’ 프레임워크를 홍보하기 위한 수단으로 보입니다.

나의 Verdict: 엔지니어를 위한 인사이트

이 긴 포스트를 다 읽고 나서 든 생각은, “이건 이론 컴퓨터 과학보다는 ‘극한의 임베디드 최적화’에 가깝다” 는 것입니다.

우리가 대규모 분산 시스템을 설계할 때도 비슷한 상황을 마주합니다. 어떤 문제는 아무리 리소스를 쏟아부어도 Latency를 줄일 수 없는 물리적/논리적 한계(Irreducibility) 에 부딪힙니다. Wolfram의 데이터는 그런 한계가 아주 단순한 튜링 머신 레벨에서도 존재한다는 것을 시각적으로 보여줍니다.

핵심 요약:

• 가치: 작은 프로그램 공간에서의 복잡도 분포를 시각화한 것은 훌륭함. $O(n)$과 $O(2^n)$ 사이의 간극을 데이터로 확인한 점은 인상적.
• 비판: P vs NP 문제의 본질적인 해결과는 거리가 멉니다. 수식보다는 관찰에 의존한 실험 리포트입니다.
• 추천: 주말에 커피 한 잔 하면서 “컴퓨팅의 본질”에 대해 멍하니 생각하기엔 좋은 글입니다. 하지만 이걸로 팀 내 알고리즘 스터디를 하지는 마세요.

Wolfram의 글은 언제나 그렇듯, 천재적인 통찰과 자기중심적인 해석이 7:3 정도로 섞여 있습니다. 걸러 들으면 꽤 맛있는 인사이트가 보입니다.