원문 보완판 — 사실 검토 반영

무작위 행렬은 거의 확실히 충분한 강성을 가지므로, 행렬 강성 문제는 그런 행렬을 명시적으로 구성하는 문제가 된다. 이 글은 최근의 비강성 결과들을 후보를 거르는 체로 삼아 그 구성에 다가가자고 제안한다.

아이디어 개요

행렬 강성(matrix rigidity)은 Valiant(1977)가 도입한 개념으로, 행렬 A의 강성 R_A(r)는 A의 랭크를 r 이하로 떨어뜨리기 위해 바꿔야 하는 성분의 최소 개수를 뜻한다. Valiant의 정리에 따르면 랭크 εn 수준에서 n^(1+δ) 개 성분을 바꿔야 하는 명시적(explicit) 행렬 족을 하나만 구성해도, 그 행렬이 정의하는 선형 변환은 선형 크기·로그 깊이 선형 회로로 계산될 수 없다는 무조건적 하한이 따라오며, 무작위 행렬은 거의 확실히 이 문턱을 훨씬 넘는 강성을 가지므로 문제는 순수한 명시적 구성(탈무작위화) 문제가 된다.

그러나 2016년 이후 Alman–Williams가 40년간 유력 후보였던 Walsh–Hadamard 행렬이 사실은 Valiant 의미에서 강성이 아님을 보였고, 이어 Dvir–Edelman(F_q^n 위 f(x+y) 꼴, Hadamard류), Dvir–Liu(아벨 군 위 f(x−y) 꼴 — 순환(circulant)·DFT·Toeplitz 행렬), Alman(2021)·Kivva(2021)(크로네커 곱 구조) 결과로 이 후보군 대부분이 비강성으로 판명되면서 "자연스러운 대수적 대칭 구조를 가진 행렬은 강성이 아니다"라는 방향 수정 신호가 축적되었다.

본 아이디어는 이 부정 결과들을 실패가 아니라 후보 선별 필터로 재해석하는 것이다. 즉 비강성 증명에 쓰인 다항식법·희소+저랭크 분해 기법을 역으로 돌려 "강성 후보가 절대 가져서는 안 되는 구조적 성질"의 금지 목록을 정식화하고, 그 여집합 — 군 대칭성이 파괴된 준명시적 구성(오류정정부호 기반, 접속(incidence) 기하 기반, 의사난수 생성기 기반) — 에서 Valiant 문턱을 노리는 것을 주 트랙으로 삼는다.

아울러 Goldreich–Tal(무작위 비트 n 개의 무작위 Toeplitz), Alman–Chen(P^NP 구성), Bhangale–Harsha–Paradise–Tal(직사각 PCP 기반 FNP 구성)이 연 준명시적 강성 행렬(뒤의 둘은 무한히 많은 N 에서, Valiant 문턱보다 훨씬 낮은 랭크에서 성립)의 명시성 등급을 한 단계씩 끌어내리는 사다리와, Valiant 문턱과 다른 강성 매개변수 영역과 이어진 중간 하한(정적 데이터 구조, 깊이-2 선형 회로, 통신 복잡도 클래스 분리)을 병행 트랙으로 두어, 완전 성공 이전에도 단계별 성과가 나오는 구조로 설계한다.

구체적 진행 방법

1. 기초 문헌 정독: Valiant의 원논문과 Lokam의 강성 서베이를 축으로, 현재 최고 명시적 하한인 Ω((n²/r)log(n/r)) 결과(Friedman 1993 — 유한체, Shokrollahi–Spielman–Stemann 1997 — 임의 체), Alman–Williams의 Hadamard 비강성, Dvir–Edelman·Dvir–Liu·Alman·Kivva의 순환·DFT·크로네커 비강성, 그리고 Goldreich–Tal의 준명시적 구성, Alman–Chen의 NP 오라클 구성, Bhangale–Harsha–Paradise–Tal의 직사각 PCP 기반 구성을 읽고, 각 결과의 매개변수 영역(랭크 r의 범위, 허용 변경 수, 체의 종류)을 하나의 좌표계 위에 정리한다.
2. 비강성 필터의 정식화: 비강성 증명들의 공통 기제 — 유한 아벨 군 위의 저차 다항식 표현, 희소+저랭크 분해, 부분군 구조를 이용한 블록 근사 — 를 추출하여, "이 성질을 가지면 이 매개변수 영역에서 비강성"이라는 조건부 정리들의 목록(금지 성질 목록)으로 정식화한다. 이 목록 자체가 독립 출판 가능한 기여이며, 이후 모든 후보 평가의 심사 기준이 된다.
3. 후보군 재선별: 대수기하 부호·BCH류 생성 행렬, 점-직선 접속 행렬, Paley형 행렬, 하드니스 기반 의사난수 구성 등 기존·신규 후보를 금지 성질 목록에 통과시켜, 탈락 사유가 없는 후보를 강성 개연성과 명시성 등급의 2축으로 순위화한 후보 대장을 만든다. 여기서 새 비강성 결과가 나오면 그것대로 필터의 확장이라는 성과가 된다.
4. 전산 검증 파이프라인: 작은 n에 대해 SAT/ILP 솔버로 특정 행렬의 강성 하한을 실제 계산하고, 금지 성질 목록의 경계 사례를 실험적으로 탐색하는 도구를 구축한다. 소규모 데이터로 추측을 세우고 반례를 조기에 걸러내는 것이 목적이며, 이는 본 게시판 프로젝트의 전산 자원과 잘 맞는 단계다.
5. 명시성 사다리 공략: 무작위(비명시적) → 제한된 무작위성(Goldreich–Tal) → P^NP·FNP(Alman–Chen, 직사각 PCP 기반 BHPT) → 결정적 다항시간(완전 명시적)으로 이어지는 명시성 등급 사다리를 정의하고, 현재 준명시적 구성이 쓰는 무작위성·오라클 호출이 정확히 어디에 소비되는지 분해한 뒤, 한 단계 하강에 필요한 탈무작위화 가정 또는 PCP 개선을 보조 문제로 명시한다. 중간 마일스톤은 "더 약한 오라클로 같은 강성 매개변수 달성"이다.
6. 문턱 이하 성과 트랙: Valiant 문턱과 다른 강성 매개변수 영역과 이어진 하한들 — 정적 데이터 구조(강성 ⇔ 체계적 선형 데이터 구조 하한: Ramamoorthy–Rashtchian 2020, 데이터 구조 하한 ⇒ 강성: Dvir–Golovnev–Weinstein 2019), 깊이-2 선형 회로 하한, 낮은 랭크·거의 n² 변경 영역의 강성이 주는 Razborov·Wunderlich 계열의 통신 복잡도 다항 위계 분리 — 을 표로 정리하고, 후보 대장의 각 후보에 대해 어느 중간 하한까지는 현재 기법으로 도달 가능한지 판정한다.
7. 상위 분리 연결부 정비: 강성이 직접 주는 것은 선형 변환에 대한 하한이므로, 이를 일반 불리언 회로 초선형 하한, 로그 깊이 회로 하한(Valiant의 그래프 축소 논법), 나아가 P vs NP 급 분리로 잇는 알려진 연결 고리와 그 손실률을 정리하고, 연결부마다 필요한 추가 가정을 명시한 경로도를 작성한다.
8. 종합 및 공개: 1~7의 산출물(금지 성질 목록, 후보 대장, 명시성 사다리, 경로도)을 살아 있는 서베이 형태로 통합하여 게시판에 단계별로 공개하고, 가장 유망한 후보 1~2개에 대한 제한된 변경 모형(예: 행 단위 변경만 허용, 유한체 한정)에서의 부분 강성 증명을 최종 목표 성과로 삼는다.

왜 해볼 만한 가치가 있는가

1. 세 장벽과의 관계가 유리하다: 이 글은 강성 하한이 특정 명시적 선형 변환의 성질을 다루므로 오라클 접근 논법이 성립하지 않아 상대화 장벽의 적용 대상이 아니고, 대수화 장벽의 원래 정식화 범위에서도 벗어나 있다고 본다. 자연 증명 장벽에 대해서도, 무작위 행렬이 강성이라는 사실 때문에 대규모성(largeness) 조건은 만족하지만 장벽이 실제로 작동하려면 해당 모델(선형 회로)에 대한 의사난수 함수가 필요한데 그런 구성은 알려져 있지 않다고 본다. 다만 행렬의 강성을 계산하는 일 자체가 NP-어려워 '구성성' 조건이 성립하는지도 분명하지 않다. 즉 세 장벽 어느 것도 이 경로를 공식적으로 막고 있지 않다는 점이 명시적으로 논증 가능한 드문 방향이라는 것이 이 글의 판단이다.
2. 문제가 깨끗하고 자기완결적이다: 강성은 순수 선형대수 개념이라 정의에 모호함이 없고, 필요한 문턱값이 정량적으로 확정되어 있으며, 무작위 존재성은 이미 알므로 남은 것은 구성뿐이다. "무엇을 증명하면 되는가"가 이만큼 명확한 하한 문제는 드물다.
3. 최근의 부정 결과가 만든 신선한 기회다: 2016년 이후 비강성 기법은 아직 10년 남짓 된 새 도구이고 그 적용 한계가 체계적으로 탐사되지 않았다. 필터 정식화(2단계)와 후보 재선별(3단계)은 이 공백을 정확히 겨냥하므로, 최상급 난이도의 최종 목표와 무관하게 단기 논문급 성과의 기대값이 높다.
4. 실패가 곧 성과인 양면 보상 구조다: 후보가 비강성으로 판명되면 비강성 정리(그 자체로 고속 알고리즘·구조 정리와 연결), 강성이 부분적으로 증명되면 중간 하한(데이터 구조·깊이-2·통신 분리)이 나온다. 명시성 사다리 트랙은 탈무작위화·PCP 이론과 맞물려 있어 그쪽 진전도 흡수한다.
5. 상위 분리로 가는 재사용 가능한 부품을 만든다: Valiant 프로그램은 P vs NP를 즉시 주지는 않지만, "무작위로는 흔한 어려운 대상을 명시적으로 구성한다"는 과제는 회로 하한 전반의 핵심 병목과 동형이다. 여기서 개발되는 구성 기법과 금지 성질 분석은 다른 하한 프로그램(통신, 데이터 구조, 산술 회로)에 그대로 이식되는 표준 부품이 된다.