LLM 수학적 추론: ChatGPT로 Erdős 60년 난제 해결 사례

서론

폴 에르되시(Paul Erdős)는 수학 역사상 가장 많은 논문을 발표한 수학자 중 한 명으로, 그가 남긴 수많은 난제들은 수십 년간 수학계를 괴롭혀왔습니다. 특히 ‘에르되시 문제 1196번’으로 불리는 조합론 문제는 정수 집합 내의 독특한 합(Sum) 속성에 관한 것으로, 지난 60년 동안 깊은 수학적 통찰력을 요구하는 미해결 과제로 남아 있었습니다. 그런데 최근 전문 수학자가 아닌 한 아마추어 연구자가 이 문제를 해결하는 파문을 일으켰습니다.

이 놀라운 성과의 핵심에는 인간의 직관과 LLM(Large Language Model)의 계산 능력을 결합한 새로운 연구 방식이 있었습니다. 단순히 ChatGPT에게 “이 문제를 풀어봐"라고 요청한 것이 아니었습니다. 이 연구자는 LLM을 ‘수학적 실험 도구’로 활용하여 가설을 검증하고, 복잡한 코드를 생성하여 방대한 경우의 수를 탐색하게 했습니다. 이 사례는 LLM이 단순한 텍스트 생성기를 넘어, 인간의 추론 능력을 확장하고 고난도의 과학적 발견을 돕는 강력한 ‘Co-pilot’이 될 수 있음을 시사합니다. 도대체 비전문가와 LLM의 협업이 어떻게 60년 난제를 해결할 수 있었을까요? 그 기술적 배경과 메커니즘을 깊이 있게 분석해 보겠습니다.

본론

신경-기호적 AI(Neuro-Symbolic AI)와 추론의 융합

LLM이 수학 문제에 약하다는 것은 잘 알려진 사실입니다. LLM은 기본적으로 다음 토큰을 확률적으로 예측하는 확률적 모델(Stochastic Parrot)이며, 정확한 논리적 연산이나 기호적 추론(Symbolic Reasoning)에는 취약하기 때문입니다. 그러나 이 아마추어 수학자의 성공 사례는 LLM의 ‘약점’을 ‘강점’으로 바꾼 신경-기호적 AI(Neuro-Symbolic AI) 접근 방식의 전형적인 예입니다.

이 접근 방식의 핵심은 LLM에게 직접 정답을 계산하게 하는 것이 아니라, **문제를 해결할 수 있는 프로그램(Python 코드)을 작성하게 하고, 그 코드를 실행하여 결과를 검증(Verification)**하게 하는 것입니다. 이는 ‘Chain-of-Thought(사슬형 사고)’ 프롬프팅을 넘어 ‘Program-Aided Language Models(PAL)’ 또는 ‘Tool-Integrated Reasoning’ 기법으로 발전한 형태입니다. LLM은 자연어 의사소통과 코드 생성 능력을 발휘하고, 실제 연산은 Python 인터프리터 같은 도구가 담당하여 hallucination(환각) 현상을 최소화하는 것입니다.

이 과정을 시각화하면 다음과 같은 인간-LLM 협업 루프가 형성됩니다.

1
2
3
4
5
6
7
8
graph TD
    A[Human: 문제 정의 및 제약 조건 설정] --> B[LLM: 가설 수립 및 수식 생성]
    B --> C[LLM: 가설 검증을 위한 Python 코드 작성]
    C --> D[Python Interpreter: 코드 실행 및 결과 도출]
    D --> E[Human: 결과 분석 및 피드백]
    E --> F{해결 여부}
    F -- No --> B
    F -- Yes --> G[최종 증명 완성 및 정제]

이 다이어그램에서 볼 수 있듯이, 핵심은 LLM이 코드를 통해 자신의 추론을 ‘검증 가능한 형태’로 외부화한다는 점입니다. 연구자는 ChatGPT에게 특정 집합의 성질을 확인하는 코드를 반복적으로 요청했고, 생성된 코드를 통해 60년 된 가설을 반증하거나 새로운 패턴을 발견해 나갔습니다.

기술적 구현: Python 기반의 조합론 탐색

실제로 이 문제 해결 과정에서 사용된 기술적 접근은 조합론(Combinatorics)적 탐색과 밀접한 관련이 있습니다. 에르되시 문제는 정수 집합의 부분 집합 합이 서로 중복되지 않는 성질을 다루므로, 이를 검증하는 알고리즘을 구현하는 것이 필수적입니다.

다음은 LLM이 생성했을 법한, 특정 집합이 ‘Distinct Sum’ 속성을 만족하는지 확인하는 Python 코드 예시입니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import itertools

def has_distinct_subset_sums(set_of_integers):
    """
    주어진 정수 집합의 모든 부분 집합의 합이 서로 다른지 확인하는 함수.
    에르되시 문제와 관련된 핵심 검증 로직.
    """
    n = len(set_of_integers)
    subset_sums = []
    
    # 모든 가능한 부분 집합 생성 (공집합 제외)
    for r in range(1, n + 1):
        for subset in itertools.combinations(set_of_integers, r):
            subset_sum = sum(subset)
            # 중복되는 합이 있는지 확인
            if subset_sum in subset_sums:
                return False
            subset_sums.append(subset_sum)
            
    return True

# 실험할 집합 예시 (연구자가 ChatGPT와 함께 최적화해 나간 값)
target_set = [3, 5, 6, 7] 
if has_distinct_subset_sums(target_set):
    print(f"Set {target_set} satisfies the condition.")
else:
    print(f"Set {target_set} does NOT satisfy the condition.")

이 코드는 매우 단순해 보이지만, LLM과의 협업에서 중요한 역할을 합니다. 연구자는 이러한 코드 스니펫을 LLM을 통해 빠르게 생성하고 수정하며, $2^n$에 비례하여 증가하는 경우의 수를 탐색합니다. 이때 LLM은 단순히 코딩을 도와주는 것을 넘어, “특정 패턴을 가진 집합을 생성하는 함수"를 작성하도록 유도됨으로써 탐색 공간을 획기적으로 축소하는 역할을 수행했습니다.

전통적 수학 연구 vs AI 기반 연구 방식 비교

이번 사례가 주는 시사점을 명확히 하기 위해, 전통적인 수학 연구 방식과 ChatGPT를 활용한 AI 기반 방식을 비교해 보겠습니다.

표에서 알 수 있듯이, AI 기반 연구는 ‘실험’을 통해 수학적 사실을 발견하는 과학적 방법론을 수학에 접목합니다. 비전문가인 연구자가 복잡한 수학 이론을 완벽히 알지 못하더라도, LLM이 제공하는 도구적 지원(Code Interpreter, Advanced Data Analysis)을 통해 고난도의 문제를 공략할 수 있는 길이 열린 것입니다.

실무 적용 가이드: LLM을 활용한 수학적 추론 최적화

이러한 성공을 본인의 연구나 프로젝트에 적용하기 위해서는 몇 가지 전략이 필요합니다. 단순히 질문하는 것을 넘어 체계적인 프롬

출처: https://www.scientificamerican.com/article/amateur-armed-with-chatgpt-vibe-maths-a-60-year-old-problem/