트로이 리가 AI 에이전트로 그래프 동형 알고리즘을 형식화했다

트로이 리(Troy Lee)가 라슬로 바바이(László Babai)의 그래프 동형 알고리즘을 형식화했습니다. 그 결과 단일 테이프 튜링 머신이 두 단순 그래프의 동형 여부를 준다항식 횟수의 전이 안에 결정한다는 증명이 나왔습니다. 알고리즘의 핵심 주장을 기계가 확인할 수 있는 증명으로 옮겼다는 점이 오래 남습니다.

Lean으로 수학적 결과를 기계가 검증할 수 있는 형태로 옮기는 흐름에 닿아 있습니다. Euler 방정식 증명도 Lean에서 검증된 사례로, 이번 결과는 알고리즘의 복잡도 증명까지 형식화 범위가 넓어졌다는 점에서 이어집니다.

수학적 주장을 형식 증명으로 옮기면, 증명 과정을 Lean이 확인할 수 있습니다. 수학적 주장을 사람이 따라 읽는 데 그치지 않고, 증명 자체를 점검할 기반이 생긴 셈입니다.

다만 이 결과가 말하는 것은 이론적 복잡도입니다. 준다항식 횟수의 전이가 실제 구현의 속도나 큰 그래프에서의 성능까지 보장하지는 않습니다. 또 증명에는 유한 단순군 분류 대신 라슬로 피베르(László Pyber)의 분석이 쓰였습니다. 따라서 어떤 분석을 바탕으로 형식화했는지도 증명의 범위를 이해할 때 중요합니다.

형식화 기록에서 증명하는 정리의 범위와 사용한 분석을 먼저 확인하십시오. 이어 코드에서 해당 정리가 어떤 가정에 기대는지 살펴보면, 형식화가 보장하는 것과 실제 알고리즘 성능의 차이가 드러납니다.

증명 자체의 기계 검증과 실제 그래프에서의 실행 성능 가운데 무엇을 먼저 확인하시겠습니까?