💻 computer science

SAT Certificates for the Matrix-Multiplication Challenges over F2: All Ten `Expected-UNSAT` Instances Are Satisfiable, and a Type-3-Free Rank-23 Scheme

이 논문은 $\mathbb{F}_2$ 상의 기존에 "기대 불만족(expected-unsatisfiable)" 상태였던 10가지 랭크-23 행렬 곱셈 공식이 모두 실제로는 만족 가능하다는 것을 입증하며, 이 사례들에 대한 완전한 증명서와 함께 타입-3-프리(type-3-free) 합산 항을 포함하는 새로운 랭크-23 스킴을 제공한다.

원저자: Nick Palladinos

게시일 2026-08-03

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Nick Palladinos

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 거대한 3차원 퍼즐을 풀고 있다고 상상해 보십시오. 하지만 이것은 일몰이나 고양이 그림이 아닙니다. 이것은 두 개의 숫자 그리드를 서로 곱하도록 설계된 수학적 기계입니다. 컴퓨터 과학과 수학의 세계에서, 이것은 "행렬 곱셈(matrix multiplication)"이라고 불립니다. 수십 년 동안 수학자들은 이 기계를 만드는 가장 효율적인 방법을 찾기 위해 추적해 왔습니다. 그들은 이 전체 장치가 작동하게 만드는 데 필요한 가장 최소한의 아주 기초적인 작은 구성 요소(이를 "곱셈"이라 부릅니다)의 개수를 알고 싶어 합니다.

이 구성 요소들을 레고 브릭이라고 생각해 봅시다. 오랫동안 우리는 3x3 곱셈 기계를 만드는 데 23개의 브릭이 필요하다는 것을 알고 있었습니다. 큰 의문은, 과연 22개만으로도 가능할 것인가 하는 점이었습니다. 이를 알아내기 위해 연구자들은 이 문제를 거대한 논리 퍼즐로 변환했습니다. 마치 비디오 게임이나 스도쿠 책에서 볼 수 있는 것과 비슷하지만, 규모 면에서는 머리가 어지러울 정도입니다. 그들은 수학의 규칙들을 컴퓨터가 확인할 수 있는 형식으로 인코딩하여 "SAT" 문제(충족 가능성 문제)를 만들었습니다. 만약 컴퓨터가 규칙을 어기지 않고 모든 스위치를 "on" 상태로 바꿀 수 있는 방법을 찾아낸다면, 그 퍼즐은 풀린 것입니다. 만약 컴퓨터가 "불가능하다"라고 말한다면, 아마도 22개의 브릭은 충분하지 않을 수도 있습니다. 이 논문은 우리의 현재 컴퓨터와 이 수학적 기계에 대한 이해의 한계를 테스트하기 위해 설계된 특정 논리 퍼즐 세트를 깊이 있게 다룹니다.

끝나지 않은 "불가능한" 퍼즐

모두가 포기했던 열 개의 논리 퍼즐을 새로운 시각으로 바라보기로 결심한 디지털 탐정, 닉 팔라디노스(Nick Palladinos)를 만나보십시오. "챌린지 2(Challenge 2)" 사례로 알려진 이 퍼즐들은 매우 구체적이고 엄격한 규칙을 가진 다른 연구자들에 의해 만들어졌습니다. 퍼즐 제작자들은 이 퍼즐들이 풀기에 "불가능하다"고 믿었습니다. 그들은 규칙이 너무 촘촘해서 23개의 레고 브릭을 조합하더라도 기계를 완성하는 것이 불가능할 것이라고 생각했습니다. 그것은 마치 "여기에 잠금장치가 달린 상자가 있는데, 이 상자는 절대로 열 수 없다"라는 말을 듣고 모두가 고개를 끄덕이며 떠나버린 것과 같았습니다.

하지만 팔라디노스는 더 큰 망치를 가져와서 억지로 자물쇠를 열려고 시도하는 대신, 자물쇠 자체를 관찰했고 결정적인 사실을 깨달았습니다. 바로 규칙이 생각만큼 엄격하지 않았다는 것입니다.

퍼즐 제작자들은 "긍정적"인 지침을 사용하여 규칙을 작성했습니다. 그들은 "여기에 반드시 이 특정 브릭이 있어야 한다"라거나 "저기에 저 브릭이 반드시 있어야 한다"라고 말했습니다. 하지만 그들은 "그리고 이 브릭들과 접촉하는 다른 브록은 있어서는 안 된다"라는 말을 빠뜨렸습니다. 알고 보니, 수학적으로는 최종 기계가 여전히 올바르게 작동하기만 한다면 추가적인 브릭을 더하는 것이 허용되었습니다. "불가능한" 퍼즐들은 사실 문이 잠겨 있었던 것이 아니라, 단지 사람들이 퍼즐 조각을 너무 작은 상자에 맞추려 했을 뿐이며, 실제로는 상자가 조금 더 커질 수 있다는 사실을 간과하고 있었던 것뿐이었습니다.

이동과 교환의 마법

그렇다면 팔라디노스는 어떻게 이 문제를 해결했을까요? 그는 "대칭성(symmetry)"을 이용한 영리한 트릭을 사용했습니다. 루빅스 큐브를 가지고 있다고 상상해 보십시오. 큐브 전체를 비틀거나 회전시켜도 색상은 움직이지만, 큐브는 여전히 동일한 물체입니다. 팔라디노스는 자신이 만들고 있는 수학적 "기계"도 이와 유사한 속성을 가지고 있다는 것을 깨달았습니다. 그는 작동하는 솔루션(행렬 곱셈을 성공적으로 수행하는 23개의 브릭 세트)을 가져와서, "GL(3, 2) 군 작용(group action)"이라는 특별한 수학적 춤을 통해 조각들을 비틀고, 회전시키고, 섞을 수 있었습니다.

이것은 방 안의 가구를 재배치하는 것과 같습니다. 소파를 왼쪽으로 옮기고, 램프를 오른쪽으로 옮기고, 카펫을 가운데에 놓을 수 있습니다. 방은 여전히 방이고 가구도 여전히 제 기능을 하지만, 배치는 달라집니다. 팔라디노스는 알려진 작동 솔루션을 가져와 이러한 수학적 "비틀기"를 적용했습니다. 그런 다음, 이 섞인 가구들이 까다로운 퍼즐이 요구하는 특정 "슬롯"에 들어맞는지 확인하기 위해 매칭 게임을 수행했습니다.

그리고 결과는 어땠을까요? 완벽하게 들어맞았습니다!

사실, 팔라디노스는 단 하나의 솔루션만을 찾은 것이 아닙니다. 그는 불가능하다고 여겨졌던 열 개 모두의 퍼즐에 대한 솔루션을 찾아냈습니다. 그는 이 "풀 수 없는" 공식들이 실제로 **충족 가능하다(satisfiable)**는 것을 증명했습니다. 컴퓨터는 단순히 추측한 것이 아니라 모든 규칙을 검사했습니다. 이 논문은 이 10개의 "챌린지 2" 파일 모두에 대해, 23개의 구성 요소를 배치하여 기계를 작동시킬 수 있는 유효한 방법이 존재함을 확인합니다. "불가능"이라는 라벨은 규칙에 대한 오해였을 뿐, 진정한 수학적 장벽이 아니었습니다.

"유령" 브릭과 완벽한 솔루션

이 논문은 세 번째 과제인 "챌린지 3(Challenge 3)"도 다루었습니다. 이 과제는 다른 질문을 던집니다. 23개의 브릭을 사용하여 기계를 만들되, 특정 브릭 하나가 "유령(ghostly)"처럼 만들 수 있는가 하는 것입니다. 수학적으로 이는 23개의 구성 요소 중 하나가 "타입-3 카운트(type-3 count)"가 0이어야 함을 의미합니다. 이것은 보통 이러한 기계에서 흔히 나타나는 특정 패턴에 해당 브릭이 참여하지 않아야 한다는 세련된 표현입니다.

팔라디노스는 이 또한 해냈습니다. 그는 작동하는 솔루션에서 시작하여 작고 정밀한 교체를 수행했습니다. 그는 특정한 역할을 수행하던 두 개의 브릭을 가져와서, 똑같은 일을 하지만 겉모습은 다른 두 개의 다른 브릭으로 교체했습니다. 이 교체는 매우 정교하여 "유령" 브릭, 즉 금지된 패턴을 전혀 트리거하지 않는 브릭을 만들어냈습니다. 그는 23개의 브릭을 사용하여 3x3 행렬 곱셈 기계를 만들 수 있으며, 그중 하나는 해당 특정 패턴으로부터 완전히 자유로울 수 있음을 증명했습니다.

최종 점검

누군가가 "컴퓨터를 써서 운 좋게 맞춘 것 아니냐"라고 말하지 못하도록, 팔라디노스는 매우 엄격한 검증기를 구축했습니다. 그는 21개의 퍼즐(챌린지 1에서 10개, 챌린지 2에서 10개, 그리고 챌린지 3에서 1개)에 대한 26,541개의 변수(스위치) 전체 목록을 생성했습니다. 그런 다음 원래의 퍼즐 규칙과 새로운 솔루션을 읽어 들여, 2,461,316개의 논리적 절(clause)을 하나하나 검사하는 별도의 프로그램을 실행했습니다.

결과는 어떠했을까요? 실패는 제로였습니다. 모든 규칙이 충족되었습니다. 솔루션은 실재하며, 검증되었고, 재현 가능합니다. 적절한 소프트웨어를 갖춘 사람이라면 누구나 동일한 코드를 실행하여 약 9초 만에 정확히 같은 답을 얻을 수 있습니다.

이것이 의미하는 바 (그리고 의미하지 않는 것)

그렇다면 핵심적인 결론은 무엇일까요? 이 논문은 "불가능한" 퍼즐들이 사실은 풀 수 있는 것이었음을 보여줍니다. 단지 규칙이 퍼즐 제작자들이 생각했던 것만큼 엄격하지 않았을 뿐입니다. 이는 수학과 컴퓨터 과학에서 때때로 가장 어려운 것은 해결책을 찾는 것이 아니라, 문제가 생각만큼 망가져 있지 않다는 것을 깨닫는 일임을 상기시켜 줍니다.

하지만 주의할 점이 있습니다. 이 논문은 "F2"라고 불리는 특정 수학 세계(숫자가 1까지만 가면 다시 0이 되는 세계, 즉 1+1=0인 세계)를 위한 퍼즐을 해결한 것입니다. 이것은 우리가 22개의 브릭으로 기계를 만들 수 있다는 것을 증명하는 것이 아닙니다. 22개 브록의 기계를 향한 여정(챌린지 4)은 여전히 미해결 상태로 남아 있습니다. 또한 이 논문은 이 솔루션들이 공학에서 사용하는 복소수와 같이 현실 세계에서 사용할 수 있는 모든 종류의 수학에서도 작동한다고 말하지 않습니다. 단지 작성된 특정 논리 퍼즐을 해결했을 뿐입니다.

하지만 작성된 퍼즐들에 대해서라면 결론은 명확합니다. "불가능"은 사실 "가능"했습니다. 문은 잠겨 있었던 것이 아니라, 우리가 손잡이를 돌릴 수 있는 올바른 열쇠를 찾기만을 기다리고 있었을 뿐입니다.

기술 요약: $\mathbb{F}_2$ 상의 행렬 곱셈 챌린지에 대한 SAT 인증서

문제 정의
본 논문은 Heule, Kauers, Seidl이 설정한 $3 \times 3$ 행렬 곱셈을 위한 rank-23 이선형 알고리즘 탐색을 인코딩한 행렬 곱셈 SAT 벤치마크를 다룹다. 이 벤치마크는 세 가지 주요 챌린지 패밀리로 구성된다:

챌린지 1: 만족 가능(satisfiable)하다고 선언되었으나 역사적으로 일반 SAT 솔버들에게 어려움을 주었던 10개의 공식.
챌린지 2: "type-3" 단항식(표준 행렬 곱셈 항)의 하드코딩된 쌍을 포함하며, 불만족(UNSAT)일 것으로 추측되었던 10개의 공식.
챌린지 3: 특정 합(summand)이 zero type-3 단항식을 포함하는 rank-23 스킴이 존재할 수 있는지 묻는 단일 공식.

핵심 수학적 객체는 729개의 cubic Brent 방정식들을 만족하는 $3 \times 3$ 행렬 곱셈 텐서의 23개 rank-one 합(summand) 분해이다. 이 방정식들은 Tseitin 변수를 통해 CNF로 인코딩되며, 결과적으로 26,541개의 변수와 240만 개 이상의 절(clause)을 가진 인스턴스를 생성한다.

방법론
저자는 전체 CNF 변수가 아닌 621개의 기본 변수( $A_t, B_t, C_t$ 계수 행렬의 엔트리들) 상에서 작동하는 "시맨틱 로컬 서치(semantic local search)" 접근 방식을 채택한다. 방법론은 세 가지 뚜렷한 단계로 진행된다:

시맨틱 서치 및 잔여 워크(Residual Walk): 알고리즘은 "잔여(residual)" 텐서(현재 rank-one 텐서들의 합과 대상 텐서 사이의 차이)를 유지한다. 이는 두 단계의 워크를 수행한다:
- 직접 복구(Direct Repair): 특정 잔여 결함을 즉각적으로 수정하는 비트(bit)를 반전시킨다.
- 이득/활성화(Gain/Activation): 미래의 상쇄를 위해 텐서를 준비함으로써 잔여 가중치를 일시적으로 증가시키는 이동을 허용하며, 이는 잔여 해밍 가중치의 변화($break - make$)에 의해 점수가 매겨진다.
  시맨틱하게 zero-residual 상태가 발견되면, 621개의 기본 변수가 할당되고 유닛 전파(unit propagation)를 통해 나머지 25,920개의 보조 Tseitin 변수들이 결정된다.
대칭 및 변환 (챌린지 2): "기대-UNSAT" 인스턴스의 경우, 본 논문은 CNF 제약 조건이 특정 type-3 인시던스(incidence)의 정확한 배제를 강제하기보다는 양의 유닛 절(positive unit clauses)을 통해 그 존재를 강제한다는 것을 보여준다. 증인(witness)을 구성하기 위해 저자는 다음을 활용한다:
- 저자는 알려진 exact 23-summand 스킴을 변환하기 위해 $GL(3, 2)^3$ isotropy 작용을 사용한다.
- 순환 트레이스 대칭 $(A, B, C) \to (B, C, A)$ 가 적용된다.
- 완벽 매칭(perfect matching) 알고리즘이 변환된 합들을 양의 유닛 절에 의해 정의된 제약된 슬롯에 할당한다.
잠금 복구 및 항등식 (챌린지 3): type-3가 없는 합 조건을 만족시키기 위해:
- 저자는 시드 솔루션(seed solution)으로부터 세 개의 특정 항을 고정한다.
- $\mathbb{F}_2$ 상의 rank-preserving 항등식이 적용된다: $92 \otimes 89 + 438 \otimes 24 = 92 \otimes 65 + 490 \otimes 24$ . 이 연산은 두 개의 합을 두 개의 다른 합으로 교체하면서 전체 텐서 합을 보존하며, 이를 통해 하나의 합을 zero type-3 단항식을 갖도록 재구성할 수 있다.

주요 기여 및 결과
본 논문은 벤치마크 저장소(commit 150b2e2f)의 모든 21개 인스턴스에 대해 완전하고 독립적으로 검증 가능한 SAT 인증서를 제공한다:

챌린지 1: 10개 인스턴스 모두 시맨틱 로컬 서치를 통해 해결되었다. 솔루션은 몇 초 만에 생성되었으며, 이는 일반적인 솔버들의 어려움이 밑바닥의 텐서 기하학이 아니라 Tseitin 인코딩에서 기인함을 입증한다.
챌린지 2: 이전에 UNSAT으로 추측되었던 10개 인스턴스가 모두 **만족 가능(satisfiable)**함이 증명되었다. 본 논문은 "하드코딩된" 쌍들이 정확한 코어(exact cores)가 아니었음을 밝혀냈다. 즉, 총 패리티(parity)가 올바른 한 추가적인 type-3 인시던스를 허용하는 구조였다. 구성된 증인들의 총 type-3 인시던스는 예상되었던 27개가 아니라 41에서 93 사이로 나타났다.
챌린지 3: 하나의 합이 type-3 카운트가 0인 유효한 rank-23 분해가 구성되었다. 이는 챌린지-3 CNF의 특정 제약을 만족한다.
검증: 별도의 파서와 절 평가기(clause evaluator)가 21개의 모델을 독립적으로 검증하였다. 검증 과정은 557,361개의 할당된 변수와 2,461,316개의 절을 확인하였으며 실패는 없었다. 결정론적인 Python 재현 도구는 약 9초 만에 모든 인증서를 재생성한다.

의의
본 논문의 주요 의의는 제공된 특정 CNF 파일들의 진릿값을 해결했다는 데 있다. 이는 다음을 확립한다:

"기대-UNSAT"인 챌린지-2 공식들은 제약 조건이 배제적(exclusive)이지 않고 포함적(inclusive, positive units)이기 때문에 만족 가능하다.
텐서 대칭 그룹과 시맨틱 구조는 일반적인 CDCL 솔버가 효율적으로 찾지 못하는 증인을 구성할 수 있게 한다.
$\mathbb{F}_2$ 상의 rank-23 스킴 내에서 type-3-free 합을 달성하는 것이 가능하다.

본 연구는 챌린지 4(rank-22 문제)를 해결하지 않으며, 임의의 환(ring) 상에서의 비가환 알고리즘을 주장하지도 않는다. 기여는 엄격히 제공된 불리언 인코딩의 만족 가능성과, 이러한 특정 인스턴스들에 대한 원시 SAT 솔빙의 한계를 우회하는 시맨틱 구성 파이프라인의 시연에 국한된다. 저자는 계산적 탐색을 위해 OpenAI GPT-5.6 Sol의 사용을 인정하지만, 수학적 주장은 독립적으로 확인 가능한 산출물들에 근거하고 있음을 강조한다.

끝나지 않은 "불가능한" 퍼즐

이동과 교환의 마법

"유령" 브릭과 완벽한 솔루션

최종 점검

이것이 의미하는 바 (그리고 의미하지 않는 것)

유사한 논문