지수 시간 가설은 틀렸다

OpenAI 명의의 논문은 임의의 고정 절 너비 k에 대해 k-CNF의 만족 할당 수를 결정론적 부분지수 시간과 다항 공간으로 정확히 계산하는 알고리즘을 제시합니다. 이 결과가 성립하면 ETH와 SETH를 비롯한 여러 계산 복잡도 가설이 반박되지만, 일반 NP 문제 전체에 부분지수 알고리즘이 생기는 것은 아닙니다.

주제: 알고리즘 이론 컴퓨터 과학 AI

에디터 노트

이 결과가 성립하면 SAT의 정확한 계수 계산에서 부분지수 알고리즘을 얻고 ETH와 SETH를 반박합니다. 다만 다항 시간 환원은 변수 수를 크게 늘릴 수 있으므로 모든 NP-완전 문제의 부분지수 풀이로 이어지지는 않습니다. 논문도 이 범위를 명시하며 그래프 색칠과 완전 매칭처럼 변수 수를 통제하는 환원 사례를 따로 듭니다. 댓글에는 이론적 파급력이 크다는 평가와 실용적 알고리즘은 아니라는 구분이 있습니다. 일부 댓글은 Anthropic 결과와 AI가 증명을 다시 만들어 냈다는 주장도 언급하지만, 여기 제시된 자료만으로는 그 주장의 근거나 논문 증명의 타당성을 확인할 수 없습니다. 따라서 구체적인 알고리즘과 복잡도 경계는 논문의 주장으로 소개하되, 성립 여부가 검증됐다고 단정하지 않는 편이 정확합니다.

AI 요약

논문은 고정된 절 너비 k를 가진 CNF 공식의 만족 할당 수를 정확히 세는 결정론적 알고리즘을 제시합니다. 정리 1.1의 일반적인 시간 복잡도는 (n+m)^{O_k(1)} 2^{O_k(n log log n / √log n)}이고, 절 수 m이 변수 수 n에 비례하는 경우에는 지수부를 O_k(n / √log n)로 낮춥니다. 공간은 입력 크기의 다항식입니다. 만족 할당 수가 0보다 큰지 확인하면 SAT 판정도 가능하므로, 논문은 ETH와 SETH를 반박한다고 주장합니다.

알고리즘 구성

먼저 변수마다 등장하는 절 수가 최대 3인 3-CNF를 다룹니다. 절을 만족 여부를 나타내는 다항식으로 바꾸고 모두 곱해 만족 할당 수를 표현합니다. 변수들을 작은 그룹으로 나누되 절이 여러 그룹에 걸쳐 얽히지 않도록, 각 절의 입력 변수를 보조 선형식으로 치환합니다. 다른 그룹의 변수에 대한 의존성은 그룹별 선형 측정값 몇 개로만 전달되게 설계합니다. 측정값을 고정하면 각 그룹의 할당을 따로 합산하고 그 결과를 곱할 수 있습니다.

치환식은 매개변수 T에 관한 저차 다항식으로 만듭니다. T=0에서는 원래 변수를 복원하고, 양의 정수 평가점에서는 그룹 간 의존성을 측정값으로 제한합니다. 각 평가점에서 치환된 다항식의 테일러 계수를 계산한 뒤 Hermite 보간으로 T=0의 값을 복원합니다. 저차 치환식을 만들 때는 교환 행렬의 고유벡터를 이용해 대부분의 방향을 보존하고, 예외 방향만 측정값으로 기록합니다. 논문은 그룹 수 r을 Θ(√log n/(log log n)^2), 평가점 수 Q를 Θ(log n/log log n), 치환 차수 R을 Θ(√log n)으로 잡아 계산량을 줄입니다.

일반적인 k-CNF에는 계수 보존형 sparsification을 적용해 여러 희소 공식으로 나눕니다. 긴 절은 보조 게이트로 3-CNF로 바꾸고, 변수 복사본에는 함의 순환을 추가해 값이 서로 같도록 강제합니다. 각 변수가 최대 세 절에 등장하는 공식으로 바꾸며, 이 변환은 만족 할당 수를 보존합니다. 논문은 더 빠른 경계를 위해 원래 변수 위에 희소한 저차 다항식 방정식계를 구성하는 방법도 제시합니다.

결과의 범위

논문은 독립 집합과 고정된 q에 대한 그래프 q-색칠 수, 완전 매칭 수에도 결정론적 부분지수 시간 알고리즘을 제시합니다. 반면 다항 시간 환원은 입력 크기를 크게 늘릴 수 있어, 이 결과만으로 모든 NP 문제에 부분지수 시간 알고리즘이 있다고 결론 내릴 수는 없다고 명시합니다. 정확한 계수 계산 결과로부터 Max-k-SAT 근사 알고리즘과 회로 하한도 도출한다고 덧붙입니다.

Lobsters 반응

@hwayne — Anthropic도 이제 #3SAT가 부분지수 시간에 풀린다는 증명을 발표했습니다.
- @agarmu — 제가 OpenAI 결과를 읽은 바로는, 논문은 모든 고정 k ≥ 2에 대해 k-CNF의 만족 할당 수를 부분지수 시간과 다항 공간으로 세는 결정론적 알고리즘을 제시합니다.
- @hwayne — 네, 그렇군요. OpenAI 논문을 제대로 읽지 못했습니다.
@cmcaine — 이 결과가 큰 의미가 있거나 다른 데 쓸모가 있나요?
- @bfiedler — 증명이 맞다면 계산 복잡도 연구에 큰 의미가 있습니다. 논문에 나온 알고리즘은 실용적이지 않지만, 놀라운 결과가 후속 발전을 촉발하는 경우가 있습니다.
@hwayne — 3-SAT가 NP-완전하다는 점을 근거로, 부분지수 알고리즘이 있으면 EXPTIME에 3-SAT보다 어려운 문제가 있다고 생각했습니다. 하지만 다항 시간 환원은 입력 크기를 키워 지수 시간 경계를 다시 만들 수 있다는 지적을 봤습니다. 논문도 일반 NP 문제 전체에 부분지수 알고리즘이 따른다고 말하지 않습니다.
@hyperpape — ETH는 P ≠ NP보다 훨씬 강한 가설입니다. 증명이 보이는 것은 2^n 알고리즘보다 점근적으로 조금 나은 알고리즘입니다.
@andyc — AI가 수학자의 긴 정의와 정리를 흉내 내기보다, 어떤 발상이 특정 정의나 정리로 이어졌는지 더 잘 설명하면 좋겠습니다. 증명이 많아질수록 증명을 설명하는 일이 더 중요해집니다.
- @jonahx — 실제로 생각에 쓸 수 있는 지식은 압축된 설명에 더 잘 담깁니다. 긴 수식의 전개보다 문제를 바꾼 발상과 적용한 정리, 결론으로 이어지는 짧은 설명이 유용할 때가 많습니다.

원문: Lobsters / 번역·요약: Trawling

원문 보기 ↗토론 보기 ↗