Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
본 기사는 계산 복잡도 이론의 핵심인 지수 시간 가설(ETH)에 대한 논의를 다룹니다. NP 문제 해결 가능성을 준지수 시간 알고리즘 관점에서 분석하며, 특히 Self-attention 메커니즘의 시간 복잡도가 SETH와 연관되어 중요한 연구 주제임을 강조합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 GeekNews의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기놀랍고 예상 밖의 결과지만, NP 전체가 준지수 시간에 풀린다는 뜻은 아님. 논문도 “2^o(n) 형태의 시간 상한은 일반적인 다항 시간 환원에서 보존되지 않으며, 그러려면 2^n^o(1)이 필요하므로 일반적인 NP 문제의 준지수 시간 알고리즘을 함의하지 않는다”고 명시함.
모든 NP 문제를 3SAT로 다항 시간에 환원할 수 있지만, 입력 크기도 다항식만큼 커질 수 있고 환원한 문제는 여전히 풀어야 함. 3SAT가 다항 시간에 풀린다면 다항식의 합성도 다항식이지만, 준지수 함수에 다항식을 합성한 결과가 준지수라는 보장은 없음.
다만 변수 수가 선형으로 증가하는 3SAT 환원이 가능한 문제에는 적용되는 듯함. 논문에서는 독립 집합 개수 세기, 올바른 q-색칠 개수 세기, 완전 매칭 개수 세기를 열거함.
k-CNF의 해 개수를 준지수 시간과 다항 공간으로 셀 수 있다면, x_1에 0과 1을 대입했을 때의 해 개수를 각각 구하고 더 큰 쪽이나 0이 아닌 쪽을 선택하면 되지 않나? 이어서 x_2=0인 경우를 세는 식으로 진행하면 될 듯함.
그러면 k-SAT의 실제 해를 찾는 데 필요한 시간은 N×준지수 시간이고 공간은 다항 공간이 되는 것 아닌가? 상수 접기까지 하면 반복마다 N도 1씩 줄어듦. 내가 놓친 당연한 사실이 무엇인지 궁금함.
지수 시간 가설(ETH) 이 거짓이라니 놀라움. 2022년 논문에는 “강한 지수 시간 가설(SETH)이 거짓이 아니라면 자기 주의(self-attention)의 시간 복잡도는 입력 길이에 대해 반드시 이차식”이라는 결과가 있음.
OpenAI의 증명이 맞다면 자기 주의를 이차 시간보다 빠르게 구현할 수 있다는 뜻인가? 결국 저렴한 하드웨어에서도 최첨단 LLM을 돌릴 수 있게 될까? 장난스럽게 표현하면 ETH가 거짓이라는 건 Nvidia에 악재인가? https://arxiv.org/abs/2209.04881
SETH가 참이면 이차 시간이라는 명제에서 SETH가 거짓이면 이차 시간이 아니라는 결론은 나오지 않음.
SETH는 ETH보다 훨씬 강한 명제임.
복잡도 클래스의 분리는 정말 드문 결과임. SAT 풀이 전문가가 이 논문의 기법에 당장 쓸 만한 응용이 있는지 알려주면 좋겠음. 실제 SAT 풀이는 보통 최악의 실행 시간과 거리가 멀어서, 실용화하기 어려운 이론적 알고리즘에 해당하는 건가?
SAT 풀이 전문가인데, 당장 활용할 방법은 없음. 논문의 결과는 실용적인 입력 규모로는 감당할 수 없는 ‘은하적 알고리즘’에 해당함. 핵심은 여기서 나온 아이디어가 다른 아이디어로 이어져, 언젠가 실용적인 기법을 만들어낼 수 있느냐임.
SAT 솔버는 입력 데이터에 따라 실제 성능이 크게 달라짐. 현실의 입력은 병적인 입력보다 훨씬 다루기 쉬운 편이라 실용적인 응용은 많지 않을 듯하지만, 아직 논문을 읽지는 않았음.
이 구성은 공간을 조회 비용이 이차식인 ‘작은’ 모델과 준지수 비용의 ‘큰’ 모델로 나눔. 작은 쪽은 모든 SAT 문제와 답을 열거해 놓고 조회하는 방식이고, 큰 쪽은 내가 이해하지 못한 다항식 관련 기법임. 경계가 어디인지 OpenAI에 물으니, 구성된 조회 기계의 상태 수가 관측 가능한 우주의 물리적으로 구별 가능한 전체 배치 수 추정치보다 훨씬 많다고 답함.
“답을 미리 전부 적어뒀으니 그 비용은 공짜”라는 것을 SAT의 이차 시간 해법으로 받아들이기는 어려움. 나머지 절반도 별로 납득되지 않음.
이것을 ETH가 거짓이라는 증명으로 인정하고 OpenAI 모델의 Lean 해석도 대략 맞는 것이라면, 나는 이 체계의 공리를 거부함. Lean이 있어도 증명으로 받아들이지 않겠으며, 이 입장 때문에 비추천을 받아도 괜찮음.
P=NP까지는 아니어도 그에 버금가는 엄청난 결과처럼 보이는데, 내가 놓친 부분이 있나?
반대로 ETH가 참임을 보였다면 P≠NP를 증명했을 것임. 3SAT는 NP에 속하며, ETH가 참이면 다항 시간에 풀 수 없기 때문임.
대신 이제 NP가 EXP의 진부분집합임을 알게 됨. NP에는 준지수 시간에 풀 수 있는 문제가 있음. 실제로 3SAT와 따라서 모든 NP 문제를 준지수 시간에 푸는 구성적 증명도 제시함. 다만 다항 시간은커녕 준다항 시간보다도 여전히 느림.
처음에는 ETH가 참이면 NP=EXPTIME이라고 썼지만 잘못된 내용이라 수정함. EXPTIME에는 NP에 속하지 않는 문제가 있을 수 있음.
아직 읽는 중이지만, 내가 제대로 이해했고 결과가 참이라면 NP가 준지수 시간에 풀린다는 뜻임. 준지수 시간이 P=NP를 뜻하지는 않지만, 사실이라면 엄청난 결과임.
어려운 문제들이 생각만큼 어렵지는 않으며 P=NP일 가능성도 여전히 열려 있음. 결국 P=NP라면 그쪽에 조금 가까워진 셈이지만, 개인적으로는 P≠NP이길 바람. ETH를 가정한 모든 논문의 결론이 이제 뒤집힐 가능성이 생김.
아주 비전문적인 해석이지만, P≠NP에 대한 확신을 약화하는 결과처럼 보임. 정말 그런지 전문가에게 듣고 싶음.
준지수 시간도 다항 시간보다 훨씬 클 수 있음. 둘 사이에는 엄청나게 넓은 간극이 있음.
널리 의존해 온 강한 지수 시간 가설과 지수 시간 가설을 무너뜨리는 결과임. 이 문제들이 쉽다는 뜻은 아니지만, 이전에 믿었던 것보다는 훨씬 쉽다는 것을 보여줌.
10년 전에 사람이 이런 결과를 발표했고 검증까지 통과했다면, 어떤 상이든 유력한 수상 후보가 됐을 것임.
이론 전산학 시간에 졸았던 사람도 이해할 수 있게 ETH를 쉽게 설명해 줄 수 있나? 친구 대신 물어봄.
이 설명이 마음에 듦. https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e.... 충족 가능성 문제는 어떤 입력 조합으로 논리식을 참으로 만들 수 있는지 판단하는 문제임. A AND NOT B는 A가 참이고 B가 거짓이면 충족되지만, A AND NOT A는 충족할 수 없음.
단순한 방법은 모든 입력 조합을 확인하는 것인데, 변수 n개라면 조합 수는 2^n개여서 지수 시간이 걸림. 지수 시간 가설은 어떤 알고리즘을 택하든 필요한 연산 수가 문제 크기에 대해 지수적으로 증가할 수밖에 없다는 추측임.
이 가설이 참이면 P≠NP가 따라옴. 충족 가능성 문제는 NP에 속하며, P에 속하려면 다항 시간 알고리즘이 있어야 하기 때문임.
복잡도 분야의 용어는 정말 혼란스러움. P는 문제 크기에 대해 다항식 횟수의 단계로 풀 수 있는 문제를 뜻하고, NP는 그렇게 풀 수 있는지는 모르지만 정답 여부는 다항식 횟수의 단계로 확인할 수 있는 문제를 뜻함.
오늘 전까지는 NP에 지수적으로 많은 단계가 필요한 문제가 있으리라는 추측이 널리 받아들여졌지만, 이제 모든 NP 문제는 기껏해야 다항식보다는 크고 지수식보다는 엄밀히 작은 시간에 풀 수 있음을 알게 됨. P=NP는 다항 시간에 검증할 수 있다면 다항 시간에 풀 방법도 있다는 뜻이고, P≠NP는 검증은 가능하지만 그렇게 풀 수는 없는 문제가 있다는 뜻임.
이번 증명은 P=NP가 더 그럴듯하게 느껴지도록 함. 다항 시간에 검증 가능한 문제에는 지수적인 단계 수가 필요할 수 없고, 초다항이면서 준지수인 단계 수는 필요할 수 있음. NP에서 가장 어려운 NP-완전 문제들이 지수 시간을 요구할 것이라 많이 추측했지만, 그렇지 않게 된 것임.
ETH는 본질적으로 NP-완전 문제의 최선의 해법도 지수 시간이라는 가설임. NP-완전 문제는 대략 각 선택지는 다항 시간에 처리할 수 있지만, 초선형으로 늘어나는 선택지 집합에서 적절한 선택을 해야 하는 문제임. 예를 들어 지도에서 총거리가 일정 한도 이하인 도시 간 경로를 찾으려면 모든 경로 선택을 훑어야 할 수 있음.
ETH는 이런 문제의 최선의 시간 복잡도가 지수적이라고 가정하는데, OpenAI가 방금 이를 반증한 셈임. 지수 시간보다는 빠르지만 여전히 다항 시간보다는 느린 해법이 가능하며, 다항 시간 해법까지 찾는다면 P=NP를 증명하게 됨.
검증은 쉽지만 풀기는 어렵다고 추측되는 문제들이 있음. 그중 3SAT는 ((a or b or c) and (b or not-c or e) and ...) 같은 식을 참으로 만드는 변수 값을 찾는 문제임. 이런 어려운 문제들은 모두 3SAT로 바꿀 수 있어서, 하나를 풀 방법을 찾으면 모두를 풀 방법도 찾게 됨.
ETH는 사실상 3SAT를 풀려면 가능한 조합을 모두 시도하는 무차별 대입이 필요하다는 뜻임. 변수가 100개라면 대략 2^100번 시도해야 함.
이번에는 무차별 대입보다 빠른 알고리즘을 찾은 것임. 3SAT가 여전히 어려운 문제일 수 있지만, 무차별 대입보다 빠른 방법을 찾는 것 자체가 큰 진전임.
3SAT는 준지수 시간에 풀 수 없다는 가설임. 개인적으로 이름을 잘 지은 추측이라고 생각한 적은 없음.
이번 결과를 계기로 ‘효율적’ 또는 ‘효율적으로 검증 가능’이라는 형식화가 현실과 동떨어져 있을 가능성과, P \in NP라는 질문 자체가 잘못 설정됐을 가능성을 진지하게 검토했으면 함.
Impagliazzo가 1990년대 중반 ‘5 worlds’ 개관을 발표한 뒤로 주변부에서 논의되어 왔고, 평균적인 경우 분석 강연이나 워크숍에서 가끔 다뤄졌지만 충분히 주목받지는 못함. 이번 결과가 검증된다는 전제하에, 이런 결과가 얼마나 더 나와야 진지하게 받아들일 것인가?
P를 효율적으로 풀 수 있는 문제, NP를 효율적으로 검증할 수 있는 문제로 간주하는 관행에 근거가 부족하다는 뜻인가? 지금까지 발견한 P의 알고리즘은 거의 모두 지수가 작았고, 미래에는 달라질 수 있어도 아직 그 사실은 변하지 않았음.
NP-난해 문제도 대부분의 입력은 어렵지 않아 실제로는 매우 효율적으로 풀리는 경우가 많음. 반대로 NP보다 ‘쉽다’고 예상하면서도 실제로는 풀기 어려운 문제들이 있고, 암호학은 거의 모두 이런 문제에 기반함. 이들은 본질적으로 NP와 co-NP의 교집합에 속하며, 그 교집합은 NP보다 작을 것으로 예상됨. 암호가 작동하려면 평균적으로도 깨기 어려워야 하므로 무작위 키도 좋은 키여야 함.
또 P는 NP의 원소가 아님. 관심사는 NP에 속하면서 P에는 속하지 않는 원소가 있는지이며, LaTeX로는 P \subset NP와 P \subseteq NP를 구분하는 질문임. 질문은 매우 명확한데, ‘잘못 설정됐다’는 것이 정확히 무슨 뜻인가?
참고로 AI와 나눈 대화에서는 앞선 표현을 이렇게 정정함. 논문은 단순히 존재를 주장하는 것이 아니라 구체적인 결정적 알고리즘과 증명된 실행 시간을 제시함. 표준적으로 인코딩된 변수 n개의 k-CNF에서 만족하는 할당의 수를 정확히 세며, 시간은 $(n+m)^{O_k(1)} \cdot 2^{O_k(n \log\log n / \sqrt{\log n})}$이고 공간은 다항식임. Lean 형식화가 이 상한을 증명하므로 단순한 이론적 존재 명제가 아님.
구현하면 종료하고 올바른 답을 내는 알고리즘이지만, 암호학적으로 관심 있는 입력 크기에서는 여전히 천문학적으로 느림. n=1,000이면 지수가 대략 1,000×5/5≈1,000으로, 2^1000 수준은 실행 가능한 계산 범위를 한참 벗어남.
환원 비용에 관한 결론도 달라지지 않음. 준지수성은 SAT 변수 수 n에 대한 것이며, 크기 N인 암호 문제를 SAT로 환원하면 n이 poly(N)으로 커져 이점을 삼킬 수 있음. 구체적인 알고리즘이라는 정정은 필요하지만, 실행 시간 상한은 암호학에 실용적 영향을 주기에는 너무 크고 원래 보안 매개변수에 대한 준지수성도 환원 과정에서 보존되지 않음.