전구 A, B, C 세 개를 켜거나 꺼서 주어진 조건을 모두 만족시켜야 하는 퍼즐이 있다고 해보겠습니다.
기호를 간단히 약속해 볼까요? 는 ‘A가 켜져 있다’는 뜻이고, (는 부정을 나타내는 기호입니다)는 ‘A가 꺼져 있다’는 뜻입니다. 우리가 지켜야 할 조건은 다음 네 가지입니다.
- 또는 또는
- 또는 또는
- 또는 또는
- 또는 또는
각 줄에 적힌 세 항목 가운데 적어도 하나가 참이면 그 줄의 조건은 통과입니다. 단, 한 줄만 통과해서는 안 되고 네 줄을 전부 만족해야 합니다.
먼저 세 전구 중 A만 켜고 B와 C는 꺼보겠습니다. 첫 번째 조건은 A가 켜져 있으니 통과입니다. 하지만 두 번째 조건은 어떨까요? A가 켜져 있으므로 ‘A가 꺼져 있다’는 뜻의 는 거짓이 됩니다. B와 C도 꺼져 있으니 와 역시 거짓이죠. 결국 세 항목이 모두 거짓이 되어 이 방법으로는 퍼즐을 풀 수 없습니다.
그렇다면 전구 하나만 상태를 바꾸어 해결할 수 있을까요?
이번에는 B도 함께 켜보겠습니다. 그러면 방금 실패했던 두 번째 조건이 덕분에 참이 됩니다. 첫 번째, 세 번째, 네 번째 조건 역시 A가 켜져 있으므로 모두 참이 되죠. 따라서 ‘A와 B를 켜고 C를 끄는 것’은 네 가지 조건을 모두 만족하는 정답 중 하나입니다.
이처럼 전구를 어떻게 켜고 끌지 미리 정해 주면, 조건을 한 줄씩 읽어 보며 정답이 맞는지 금방 확인할 수 있습니다. 설령 정답을 모르더라도 전구가 세 개뿐이라면 일일이 스위치를 바꿔 가며 답을 찾을 수 있죠. 하지만 퍼즐이 훨씬 거대해진다면 어떨까요? 조건 한 줄은 지금처럼 세 항목으로 이루어져 있지만, 그런 줄이 수없이 많이 이어질 수 있습니다. 전구가 백 개, 천 개로 늘어나고 복잡한 조건들이 주어졌을 때, 우리는 어떻게 답을 찾아야 할까요?
경우의 수가 늘어나면
전구 하나당 선택할 수 있는 상태는 ‘켜짐’과 ‘꺼짐’ 두 가지입니다. 전구가 세 개면 전체 경우의 수는 가지입니다. 여기에 전구 D를 하나 더 추가하면, 기존의 여덟 가지 경우마다 D를 켜거나 끄는 두 가지 선택이 각각 붙습니다. 따라서 가능한 경우의 수는 두 배인 가지가 됩니다.
전구가 하나씩 늘어날 때마다 똑같은 일이 벌어집니다. 전구가 열 개면 가지, 스무 개면 가지로 불어납니다. 즉, 전구가 개일 때 가능한 모든 조합은 가지입니다. 이 조합을 전부 만들어 하나씩 검사하는 방법은 전구 수가 늘어날수록 확인해야 할 후보가 감당할 수 없을 만큼 폭발적으로 증가합니다.
그렇다고 모든 경우를 똑같이 일일이 검사해야만 할까요? 전구가 네 개인 퍼즐에도 맨 처음 보았던 “A 또는 B 또는 C”라는 조건이 들어 있다고 생각해보겠습니다. 만약 A, B, C가 모두 꺼져 있다면, D가 켜져 있든 꺼져 있든 이 조건은 무조건 실패합니다. 굳이 나머지 조건들을 읽어 볼 필요도 없이, D의 상태만 다른 두 가지 경우를 한꺼번에 탈락시킬 수 있는 셈입니다. 이처럼 조건의 구조를 잘 활용하면 후보를 하나씩 무작정 검사하는 수고를 크게 덜 수 있습니다.
결국 ‘후보의 수가 엄청나게 많다’는 사실과 ‘어떤 방법을 쓰더라도 풀이 시간이 오래 걸린다’는 주장은 전혀 다른 이야기입니다. 하나씩 다 해보는 무식한 방법보다 얼마나 더 영리하게 문제를 풀 수 있는지가 핵심으로 남습니다.
2026년 10월 26일 OpenAI가 공개한 ‘지수시간 가설(ETH)의 반증’ 주장은 바로 이런 논리 퍼즐을 푸는 데 걸리는 시간에 관한 연구입니다. 이 결과가 컴퓨터과학에서 무엇을 바꾸었는지 제대로 이해하려면, 먼저 ‘문제를 빠르게 푼다’는 기준부터 명확히 짚어 보아야 합니다.1
얼마나 빨라야 빠른 걸까?
똑같은 풀이 방법이라도 성능이 좋은 슈퍼컴퓨터로 돌리느냐, 오래된 노트북으로 돌리느냐에 따라 실제 걸리는 시간(몇 초)은 달라집니다. 그래서 컴퓨터과학에서는 풀이 방법의 효율성을 비교할 때, 문제의 크기가 커짐에 따라 컴퓨터가 해야 할 작업량이 얼마나 늘어나는지를 따집니다.
예를 들어 명단에서 특정한 사람의 이름을 찾는 상황을 떠올려보겠습니다. 이름 하나를 대조하는 일을 작업 1번으로 세면, 명이 적힌 명단은 최악의 경우라도 번만 대조하면 됩니다. 명단 길이가 두 배로 늘어나면 작업량도 딱 두 배가 됩니다.
이번에는 각각 명이 적힌 두 명단에서 만들 수 있는 모든 짝을 확인해보겠습니다. 첫 번째 명단의 한 사람마다 두 번째 명단의 명을 모두 짝지어 보아야 하므로, 살펴볼 짝은 총 개입니다. 각 명단의 인원이 10명에서 20명으로 두 배 늘어나면, 확인해야 할 짝은 100개에서 400개로 네 배가 됩니다.
반면 앞에서 본 전구 퍼즐의 모든 경우를 하나씩 검사한다면 어떨까요? 전구가 개일 때 후보가 가지이므로, 전구가 10개에서 20개로 두 배 늘어나면 후보 수는 에서 으로 무려 1,024배나 뜁니다. 인원이 두 배 늘 때 작업량이 두 배(), 네 배()로 늘어나는 것과 비교하면, 전구 퍼즐의 후보 수는 차원이 다르게 빠르게 증가합니다.
여기서 컴퓨터에 문제를 입력하기 위해 기록하는 전체 데이터 길이를 입력 크기라고 부릅니다. 명단 문제라면 사람 수뿐만 아니라 각 사람의 이름을 적는 글자 수까지 포함되고, 전구 퍼즐이라면 전구 번호와 조건들을 모두 적어 놓은 전체 길이가 입력 크기가 됩니다.
이 입력 크기 에 대해 전체 계산 횟수를 고정된 차수의 다항식으로 제한할 수 있을 때, 우리는 이 문제를 다항시간(polynomial time)에 풀 수 있다고 말합니다. 예를 들어 계산 횟수가 번 이내에 끝나거나 번 이내에 끝나는 알고리즘이 여기에 해당합니다. 이때 식의 차수나 계수는 입력이 커진다고 함께 커지는 값이 아니라, 그 풀이 방법에 대해 미리 딱 정해진 상수여야 합니다. 또한 같은 크기의 입력 중 운이 가장 나빠서 오래 걸리는 ‘최악의 경우’에도 이 한계를 넘지 않아야 합니다.2
답을 받았을 때와 받지 않았을 때
앞에서는 전구를 켜고 끄는 전체 경우의 수를 세어 보았습니다. 이번에는 누군가 각 전구의 상태를 미리 알려 주었을 때, 그 상태가 모든 조건을 만족하는지 검증하는 데 필요한 작업량을 세어보겠습니다.
처음 퍼즐은 조건이 네 줄이고 각 줄에 항목이 세 개씩 있었습니다. 모든 항목을 다 읽어도 번이면 충분합니다. 한 줄에서 참인 항목을 앞쪽에서 일찍 발견하면 그 줄의 나머지는 읽을 필요조차 없죠. 조건이 여덟 줄이면 많아야 번, 줄이면 많아야 번만 확인하면 됩니다. 전구의 현재 상태를 찾아 읽는 과정까지 모두 포함하더라도, 제시된 후보 하나가 정답인지 확인하는 계산은 전구 번호와 조건들을 적은 전체 입력 길이의 다항식 안에서 충분히 끝납니다.2
앞서 찾았던 ‘A와 B를 켜고 C를 끄는 방법’은 이 퍼즐에 답이 존재한다는 확실한 증거가 됩니다. 우리가 직접 어떤 전구를 켤지 머리 싸매고 찾아내지 않더라도, 누군가 이 증거를 건네주면 조건들을 대입해 보고 답이 있다는 사실을 순식간에 검증할 수 있습니다.
수학적으로 엄밀하게 정의하면, P와 NP는 ‘조건을 만족하는 답이 있는가?’처럼 ‘예’ 또는 ‘아니오’로 대답할 수 있는 판정 문제들의 모임(집합)입니다. 전구 퍼즐에서는 조건을 만족하는 전구 상태 하나가 바로 ‘예’라는 대답의 증거가 됩니다. 전구마다 켜짐·꺼짐만 기록하면 되므로 증거의 길이도 그리 길지 않습니다.
이처럼 답이 ‘예’인 문제에 대해 짧은 증거가 존재하고, 그 증거가 맞는지 다항시간 안에 확인할 수 있는 문제들의 모임이 NP입니다. 물론 증거의 길이 역시 입력 크기의 다항식 이내여야 합니다. 흔히 NP를 ‘다항시간에 풀 수 없다(Non-Polynomial)’의 약자로 오해하기 쉽지만, 전혀 그렇지 않습니다. NP는 정답을 직접 찾는 시간이 아니라, 주어진 증거를 확인하는 시간을 기준으로 정의한 개념입니다.2
반면 P는 누군가에게 증거를 건네받지 않고도, 처음부터 스스로 계산해서 다항시간 안에 ‘예·아니오’를 판정할 수 있는 문제들의 모임입니다. 명단에 특정 이름이 있는지 찾는 문제는 누군가 위치를 귀띔해 주지 않아도 명단을 처음부터 끝까지 훑어보면 금방 답을 낼 수 있죠. 이처럼 직접적인 빠른 풀이가 존재하는 것이 P의 조건입니다.
당연히 P에 속하는 모든 문제는 NP에도 속합니다. 누군가 답이 ‘예’라고 주장하면, 굳이 증거를 받지 않더라도 원래 가지고 있던 빠른 풀이법을 직접 실행해서 확인하면 되기 때문입니다. 이 포함 관계를 기호로 라고 나타냅니다.2
여기서 주의할 점이 있습니다. P와 NP는 ‘전구 세 개짜리 특정 퍼즐 하나’를 분류하는 이름이 아닙니다. 전구와 조건의 개수가 아무리 달라져도 같은 규칙과 형식으로 주어지는 문제 전체를 어떤 방식으로 처리할 수 있는지에 관한 분류입니다. 또한 답이 있으면 P이고 없으면 NP라는 뜻도 아닙니다.
전구 퍼즐의 경우, ‘답이 존재하는지 알아내는 일’과 ‘실제 정답을 찾아내는 일’은 서로 연결되어 있습니다. 퍼즐에 답이 있는지 다항시간 안에 알려 주는 마법 같은 기계가 있고, 현재 주어진 퍼즐에 답이 있다고 해보겠습니다. 먼저 전구 A를 꺼 둔 상태로 기계에 “아직도 답이 있나요?”라고 묻습니다. “예”라고 하면 A를 끈 채로 확정하고, “아니오”라고 하면 A를 켭니다. 그다음 A를 고정한 채 전구 B에 대해서도 똑같이 질문합니다. 이런 식으로 전구 하나씩 차례대로 물어보면, 결국 어떤 전구를 켜고 꺼야 하는지 실제 정답까지 다항시간 안에 찾아낼 수 있습니다.2
이제부터는 설명을 간단히 하기 위해, 주어진 전구 상태가 조건을 만족하는지 살피는 일을 ‘답을 확인한다’, 조건을 만족하는 전구 상태를 직접 구하는 일을 ‘답을 찾는다’(답이 없다면 없다고 밝혀내는 것 포함)라고 부르겠습니다.
그러면 컴퓨터과학 최대의 난제인 P 대 NP 문제는 다음과 같이 한 문장으로 요약됩니다.
“답을 빠르게 확인할 수 있는 문제(NP)는, 답을 찾는 것도 빠르게 할 수 있을까(P)?”
모든 NP 문제에 대해 이것이 가능하다면 가 됩니다.
전구 퍼즐 하나가 왜 중요할까?
처음 퍼즐에서 보았던 것처럼 세 항목을 ‘또는’으로 연결한 조건 한 줄을 논리학에서는 절(clause)이라고 부릅니다. 그리고 이런 절들이 여러 개 주어졌을 때 모든 조건을 만족하는 답을 찾는 전구 퍼즐이 바로 3-SAT입니다.
전구 퍼즐의 규칙은 생각보다 표현력이 뛰어납니다. 예를 들어 “전구 A와 B를 동시에 켜면 안 된다”는 규칙도 같은 형식으로 바꿀 수 있습니다. 둘을 동시에 켜지 않으려면 A와 B 중 적어도 하나는 꺼져 있어야 하므로, 조건은 ‘ 또는 ’가 됩니다. 여기에 같은 항목을 한 번 더 적어 ‘ 또는 또는 ’라고 쓰면 의미는 똑같으면서 항목 세 개짜리 절의 형태를 완벽히 갖추게 됩니다.
놀라운 점은 3-SAT로 바꿀 수 있는 문제가 단순한 전구 퍼즐에 그치지 않는다는 것입니다. NP에 속하는 문제라면 세상의 어떤 문제든 3-SAT의 전구와 조건들로 바꿀 수 있다는 정리가 이미 수학적으로 증명되어 있습니다. 원래 문제에 답이 있으면 변환된 전구 퍼즐에도 답이 있고, 원래 문제에 답이 없으면 변환된 퍼즐에도 답이 없습니다.
게다가 이 정리는 문제를 변환하는 데 걸리는 시간까지 보장해 줍니다. 어떤 NP 문제든 입력을 3-SAT 퍼즐로 바꾸는 과정 자체가 다항시간 안에 끝나며, 변환되어 만들어진 전구와 조건들의 전체 길이 역시 원래 입력 크기의 다항식 이내로 유지됩니다.
따라서 만약 누군가 3-SAT를 다항시간에 푸는 프로그램을 개발한다면, 다른 모든 NP 문제도 먼저 3-SAT로 변환한 뒤 그 프로그램에 넣어서 다항시간 안에 답을 구할 수 있습니다.
바로 이 이유 때문에 3-SAT에는 NP-완전(NP-complete)이라는 특별한 이름이 붙습니다. ‘완전’이라고 부르는 까닭은, 다항시간 변환을 거쳐 NP에 속한 모든 문제를 3-SAT 하나로 대신 풀 수 있기 때문입니다.
여러 가지 형식의 동영상 파일을 MP4로 변환해서 재생하는 상황을 떠올려 보면 이해가 쉽습니다. 원래 영상들의 파일 형식이 AVI, MOV, MKV 등으로 제각각이더라도 전부 MP4로 바꿀 수만 있다면, 우리에게는 MP4 재생기 단 하나만 있으면 됩니다. 원래 형식마다 전용 재생기를 따로 설치할 필요가 없죠.
문제 풀이 세계에서 이 MP4와 같은 공통 표준 역할을 하는 것이 바로 3-SAT입니다. 다양한 원래 영상 형식들이 NP에 속한 여러 문제들이라면, 이들을 한데 모으는 MP4가 3-SAT인 셈입니다. 그래서 3-SAT 전용 풀이 프로그램 하나만 만들어 두면, 다항시간 변환을 거쳐 다른 모든 NP 문제를 그 프로그램으로 해결할 수 있습니다. 핵심은 변환을 거친 뒤 ‘단 하나의 풀이 도구’로 전부를 처리할 수 있다는 점입니다.
정리하자면 NP와 NP-완전은 다음과 같이 구별됩니다.
- NP: 주어진 답(증거)을 다항시간 안에 확인할 수 있는 문제들의 모임입니다.
- NP-완전: NP에 속하면서, 다항시간 변환을 통해 다른 모든 NP 문제의 풀이까지 대신 맡을 수 있는 대표 문제들입니다.
물론 3-SAT뿐만 아니라 NP에 속한 다른 문제라도 모든 NP 문제를 자신으로 다항시간에 변환할 수 있다는 사실이 증명되면 똑같이 NP-완전이라고 부릅니다.2
아직까지 3-SAT를 다항시간에 푸는 방법은 세상에 알려져 있지 않습니다. 만약 3-SAT의 다항시간 풀이법이 발견된다면, ‘문제 변환’부터 ‘3-SAT 풀이’까지의 전체 과정이 다항시간에 끝나므로 모든 NP 문제를 다항시간에 풀 수 있게 됩니다. 즉, 가 증명되는 것입니다. 3-SAT 문제 하나의 빠른 풀이가 다른 모든 NP 문제의 빠른 풀이로 직결된다는 점이 바로 이 퍼즐이 가진 엄청난 무게감입니다.
ETH가 예상한 시간 장벽
P 대 NP 문제가 ‘다항시간 풀이가 존재하는가?’를 묻는다면, ETH(Exponential Time Hypothesis, 지수시간 가설)는 같은 3-SAT 문제에 대해 훨씬 더 깐깐하고 구체적인 시간 장벽을 예상한 가설입니다.
앞의 퍼즐은 전구가 세 개이고 조건이 네 줄이었습니다. 그런데 전구 개수는 세 개로 똑같더라도 조건을 수십, 수백 줄씩 더 붙이면 컴퓨터가 읽어야 할 전체 데이터 길이는 훨씬 길어집니다. 따라서 ‘전구의 개수’와 ‘전구 번호 및 조건들을 모두 적은 전체 길이’는 서로 다른 값입니다. 다항시간을 정의할 때는 전체 데이터 길이를 기준으로 삼았지만, ETH에서는 전구(즉, 변수)의 개수 을 기준으로 계산량이 얼마나 늘어나는지를 살핍니다.
누군가 전수검사()보다 훨씬 영리한 알고리즘을 개발해서 계산량을 수준까지 줄였다고 가정해보겠습니다. 전구가 100개일 때 번 계산할 것을 번으로 줄였으니 어마어마한 발전입니다. 하지만 전구를 딱 두 개만 더 늘려도 계산량은 다시 두 배가 됩니다.
또한 이므로, 지수의 밑이 에서 로 작아졌을 뿐 여전히 에 따라 지수적으로 증가하는 형태를 벗어나지 못했습니다.
ETH는 바로 이 지점을 짚습니다. “3-SAT를 푸는 알고리즘을 아무리 영리하게 개선하더라도, 최악의 경우에는 어떤 고정된 양의 지수율(, 단 )을 결코 피할 수 없다”는 것이 ETH의 주장입니다. 즉, 보다 조금 빨라질 수는 있어도 지수함수적인 증가 자체에서는 절대 벗어날 수 없으리라고 본 것입니다.3
두 시간 기준은 다음처럼 연결됩니다. 같은 조건을 반복해 적어도 답은 바뀌지 않으므로, 그런 조건은 한 번만 남길 수 있습니다. 전구가 개일 때 세 항목으로 만들 수 있는 서로 다른 조건은 가지 이하이고, 전구 번호를 적는 길이까지 포함해도 전체 기록 길이는 의 다항식 이내입니다. 따라서 입력 길이에 대한 다항시간 풀이가 있다면, 정리된 문제에서는 전구 수를 기준으로도 다항시간에 풀 수 있습니다. 반복된 조건을 읽고 정리하는 준비 작업은 원래 입력 길이의 다항시간 안에서 할 수 있습니다.
만약 ETH의 주장이 참이라면 는 절대 성립할 수 없습니다. 거꾸로 가 참이라면 ETH는 거짓이 됩니다. 하지만 여기서 매우 중요한 논리적 함정이 하나 있습니다. ETH가 거짓으로 밝혀졌다고 해서 곧바로 다항시간 풀이()를 얻는 것은 아니라는 점입니다. 지수시간과 다항시간 사이에는 여전히 넓은 간극이 남아 있기 때문입니다.
flowchart TD A["P = NP라고 가정"] --> B["3-SAT는 NP이므로<br/>P에도 속함"] B --> C["3-SAT의 답을<br/>다항시간에<br/>찾을 수 있음"] D["ETH가 참이라고 가정"] --> E["3-SAT의 지수적인<br/>시간 증가는 불가피"] E --> F["3-SAT의 답을<br/>다항시간에<br/>찾을 수 없음"] C --> G["두 결론이 충돌<br/>동시에 참일 수 없음"] F --> G classDef possible fill:#eff6ff,stroke:#2563eb,color:#0f172a classDef impossible fill:#fff7ed,stroke:#c2410c,color:#0f172a classDef conflict fill:#fef2f2,stroke:#dc2626,color:#7f1d1d class C possible class F impossible class G conflict
지수와 다항 사이
전구가 개일 때 계산 횟수가 인 알고리즘이 있다고 상상해 보겠습니다. 앞서 본 에서는 지수에 의 절반()이 그대로 남아 있었습니다. 반면 이므로, 의 지수는 에 을 곱한 모양입니다. 이 비율 은 전구 수 이 커질수록 에 한없이 가까워집니다. 따라서 아무리 작은 양수 를 가져오더라도, 이 충분히 커지면 이 되어 이 성립합니다. 이 글에서는 어떤 양수 를 정해도 충분히 큰 에서 보다 느리게 증가하는 것을 준지수적(subexponential)이라고 부르겠습니다. 다항식도 이 범위에 포함되지만, 지금 예로 든 이 다항식만큼 작은지는 따로 비교해야 합니다.
그렇다면 은 우리가 원하는 다항시간만큼 충분히 작아진 걸까요? 대표적인 다항식 과 직접 숫자를 넣어 비교해 보겠습니다.
- 일 때: 이고, 입니다. 준지수 쪽이 4배 더 큽니다.
- 로 늘리면: 이고, 입니다. 이번에는 무려 약 2억 7천만 배() 차이로 벌어집니다.
전구 수 을 네 배 늘리는 동안 두 계산량의 격차가 엄청나게 커졌습니다. 물론 세제곱보다 차수가 훨씬 큰 같은 다항식과도 비교해 보아야 확실히 알 수 있겠죠.
다항식의 차수 를 어떤 큰 자연수로 고정하고, 라고 놓아 보겠습니다. 두 계산량을 모두 밑이 2인 거듭제곱으로 고치면 지수인 와 의 크기 비교가 됩니다.
가 씩 커질 때마다 다항식의 지수 는 만큼 일정하게 더해지지만, 준지수식의 지수 는 매번 두 배씩 곱해집니다. 따라서 차수 를 아무리 거대하게 잡더라도, 충분히 큰 에서는 결국 가 되어 가 됩니다.
이 딱 꼴이 아닌 일반적인 자연수()일 때도 마찬가지입니다. 는 범위의 오른쪽 끝값을 넣어 더 크게 만들고, 은 왼쪽 끝값을 넣어 더 작게 만든 뒤 비교해 보겠습니다.
여기서도 가 커짐에 따라 는 두 배씩 폭증하고 은 일정한 간격으로만 늘어납니다. 결국 충분히 큰 에서는 이 성립하므로, 최대한 크게 잡아 준 보다 최대한 작게 잡아 준 이 훨씬 더 커집니다.
결론적으로 은 차수가 고정된 그 어떤 다항식보다도 빠르게 커집니다. 지수시간 장벽을 깼다고 해서 다항시간 영역까지 내려온 것은 아니라는 뜻입니다. 만약 누군가 3-SAT를 수준으로 푸는 방법을 찾았다면 ETH의 예상을 깬 것은 맞지만, 그 풀이 역시 다항식보다는 훨씬 무겁기 때문에 다항시간 풀이를 얻었다고 할 수는 없습니다.
반대로, 그렇다고 해서 앞으로 더 빠른 풀이가 영영 없다는 뜻도 아닙니다. 어떤 알고리즘에 필요한 계산량이 ‘아무리 많아야 이 정도 선을 넘지 않는다’고 보장해 주는 한계치를 상계(upper bound)라고 부릅니다. 준지수시간 알고리즘을 발견했다는 것은 기존의 지수시간보다 더 낮은 새로운 상계를 하나 확보했다는 의미일 뿐, 미래에 다항시간 알고리즘이 등장할 가능성까지 가로막는 것은 아닙니다.
따라서 ETH의 반증만으로는 도, 도 결정되지 않습니다. 실제로 밀레니엄 난제를 주관하는 클레이 수학연구소 역시 P 대 NP 문제를 여전히 미해결 문제로 두고 있습니다.4
가설이 바뀐 뒤에 남는 연구
지금까지는 조건을 만족하는 답을 하나 찾는 과정을 살펴보았습니다. 이번에 공개된 OpenAI 논문은 한발 더 나아가, 조건을 모두 만족하는 정답이 총 몇 가지인지 정확히 세는 알고리즘을 제시합니다. 정답의 개수가 이면 답이 없는 것이고, 이상이면 답이 존재하는 것이니, 개수를 셀 수 있으면 당연히 답의 존재 여부도 알 수 있습니다.
논문은 한 줄(절)에 들어가는 항목 수를 세 개(3-SAT)뿐 아니라 임의의 고정된 수 개로 일반화한 경우까지 다룹니다. 전구 수를 , 조건의 줄 수를 , 한 줄의 항목 수를 라고 할 때, 논문이 증명한 계산 시간의 상계는 다음과 같습니다(3-SAT의 경우 입니다).3
이 식에서 시간 증가 속도를 결정짓는 핵심은 뒤쪽의 거듭제곱 부분입니다. 지수에서 에 곱해진 비율을 보면 인데, 분모의 이 분자의 보다 훨씬 빠르게 커지기 때문에 이 커질수록 이 비율은 에 수렴합니다. 또한 똑같이 반복되는 중복 조건들을 정리하면 조건의 줄 수 역시 의 다항식 이내로 제한되므로, 앞쪽에 곱해진 다항식 요인 까지 모두 합쳐도 전체 계산 시간은 여전히 준지수적입니다. 바로 이 지점이 논문이 달성한 새로운 상계와 기존 ETH가 그어 놓았던 지수시간 장벽 사이의 결정적인 차이입니다.
OpenAI는 논문과 함께, 주요 결과를 형식적인 명제와 증명으로 옮겨 컴퓨터가 검사하도록 한 Lean 형식화 자료도 공개했습니다. 이 검사는 형식화된 명제와 증명을 대상으로 하므로, 그 명제가 자연어 논문의 주장과 어디까지 일치하는지는 따로 대조해야 합니다. 공식 범위 문서에 따르면 형식화에서는 논문보다 느슨한 시간 상계를 보장하지만, 두 식 모두 준지수적으로 증가합니다.5
그렇다면 이 주장이 최종적으로 참으로 확정될 경우, 그동안 ETH가 참이라고 믿고 쌓아 올린 수많은 후속 연구들은 어떻게 될까요?
예를 들어 기존에 어떤 학자가 “만약 문제 X를 아주 빠르게 풀 수 있다면, 그 풀이법을 이용해서 3-SAT도 준지수시간에 풀 수 있다”라는 연결 관계를 증명했다고 해보겠습니다. ETH를 믿던 시절에는 3-SAT가 절대 준지수시간에 풀리지 않을 것이라고 보았기 때문에, 이를 근거로 “문제 X 역시 빠른 풀이가 존재하지 않을 것”이라고 결론 내릴 수 있었습니다.
ETH가 반박되면 “문제 X에 빠른 풀이가 없을 것”이라고 판단했던 근거는 사라집니다. 하지만 두 문제를 서로 연결해 놓았던 논리적 다리(변환 증명) 자체까지 틀린 것이 되는 건 아닙니다. 문제를 어떤 방향으로 변환했는지, 변환할 때 데이터 크기가 얼마나 늘어났는지, 그 과정에서 어떤 알고리즘 기법을 썼는지는 여전히 유효한 지식으로 남습니다. 단지 ETH를 전제로 내렸던 최종 결론이 참인지 거짓인지만 새로운 기준에 맞춰 다시 따져 보면 되는 것입니다.6
AFP 통신과의 인터뷰에서 ETH의 제안자 중 한 명인 라마모한 파투리(Paturi)는 놀라움을 감추지 못하면서도, ETH를 토대로 쌓아 온 기존 연구 성과가 한순간에 물거품이 되는 것은 아니라는 취지로 말했습니다. 공동 연구자인 라이언 윌리엄스(Williams) 역시 이 결과가 최종 검증된다면 그동안 불가능하다고 여겼던 더 효율적인 계산 방법을 찾아낼 새로운 가능성이 열릴 수 있다고 내다보았습니다.7 기존 연구를 다시 점검하는 작업과 완전히 새로운 알고리즘을 탐색하는 작업이 동시에 활기를 띠게 된 이유입니다.
다만 3-SAT의 새로운 준지수시간 알고리즘이 나왔다고 해서, 다른 모든 NP 문제들이 저절로 준지수시간에 풀리게 되는 것은 아닙니다. 앞서 다항시간을 다룰 때는 변환 후의 크기가 원래 입력 크기의 다항식 이내이기만 하면 전체 과정도 다항시간이 보장되었습니다. 하지만 준지수시간에서는 사정이 다릅니다.
원래 입력 길이가 인 어떤 문제를 다항시간 변환을 거쳐 3-SAT로 바꾸었더니, 전구(변수)의 개수가 개로 늘어났다고 가정해 보겠습니다. 여기에 계산량이 인 준지수시간 알고리즘을 적용하면 어떻게 될까요?
3-SAT의 변수 수 을 기준으로 볼 때는 분명 준지수적이었던 계산량이, 원래 문제의 입력 크기 을 기준으로 되돌려 놓으니 다시 지수시간()이 되어 버렸습니다. 이처럼 문제 변환 과정에서 변수 개수가 제곱, 세제곱 등으로 늘어나면 준지수시간의 이점이 상쇄될 수 있기 때문에, 3-SAT가 풀렸다고 모든 NP 문제가 곧바로 준지수시간에 풀리는 것은 아닙니다.3
이제 연구자들은 기존의 문제 변환 과정을 꼼꼼히 되짚어 보며, 변환할 때 변수 개수를 덜 늘리는 더 정교한 길은 없는지 다시 묻기 시작할 것입니다. 나아가 새로 발견된 알고리즘의 핵심 아이디어를 변형해 다른 난제들에도 이점을 남길 수 있을지, 계산량을 여기서 더 깎아내릴 수 있을지도 연구할 수 있습니다.
우리는 글의 맨 처음에서 전구 퍼즐의 조건을 이용해 불필요한 후보들을 한꺼번에 건너뛰는 아이디어를 떠올려 보았습니다. 거대한 문제에서도 조건의 구조를 어떻게 꿰뚫어 보고 활용하느냐에 따라, 인류가 철석같이 믿어 온 시간의 장벽이 무너질 수 있습니다. 가설이 바뀐 뒤에 남겨진 연구는, 그동안 쌓아 온 연결 고리와 새로운 계산 기법을 무기로 그 가능성의 끝이 과연 어디까지 이어지는지 확인하는 여정이 될 것입니다.
Footnotes
-
OpenAI, Working with academic communities to build scientific understanding, 2026-10-26 — 2026-10-26, The Exponential Time Hypothesis is false 절. ↩
-
Stephen Cook, The P versus NP Problem, CMI 공식 문제 설명 — pp.1–5, 다항시간·P·NP의 정의, 포함 관계, NP-완전성과 SAT·3-SAT. ↩ ↩2 ↩3 ↩4 ↩5 ↩6
-
OpenAI, The Exponential Time Hypothesis is False, 2026-10-17; revised 10-25 — 2026-10-25 판본, pp.1–2, Theorem 1.1 및 일반 NP 문제로의 환원에 관한 문단. 고정된 , 에서의 비트 연산 횟수 상계는 이며, 은 변수 수, 은 절 수입니다. ↩ ↩2 ↩3
-
Clay Mathematics Institute, P vs NP — Unsolved 표기, 2026-11-09 확인. ↩
-
OpenAI, Lean formalization scope, The Exponential Time Hypothesis is False — Scope 두 문단. 형식화된 상계의 지수에는 이 들어가며, 10월 25일 논문의 더 날카로운 상계와 구별합니다. ↩
-
Impagliazzo, Paturi, Williams, ETH Refutation: Examination and Discussion, 2026-10-26 — 2026-10-26, 첫 두 문단과 기존 아이디어·환원·기법의 가치에 관한 문단. ↩
-
AFP, Impagliazzo·Paturi·Williams 공동 인터뷰, Malay Mail 전재, 2026-10-31 — 2026-10-31, Surprise·Possibilities 문답. 길이와 명료성을 위해 편집된 인터뷰입니다. ↩