대수화 장벽 — 산술화로도 넘지 못하는 선

산술화는 상대화 장벽을 넘었고, 대각선 논법과 결합해 자연 증명 장벽까지 피하는 회로 하한을 낳았다. Aaronson 과 Wigderson 은 오라클에 저차 다항식 확장을 붙여 주어도 통하는 논증으로는 P vs NP 나 NEXP ⊄ P/poly 를 증명할 수 없음을 보였다.

전문
관리자
2026-10-05 23:05
조회 0
AI 도움

검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

산술화는 상대화 장벽을 넘었고, 대각선 논법과 결합해 자연 증명 장벽까지 피하는 회로 하한을 낳았다. Aaronson 과 Wigderson 은 오라클에 저차 다항식 확장을 붙여 주어도 통하는 논증으로는 P vs NP 나 NEXP ⊄ P/poly 를 증명할 수 없음을 보였다. 이 글은 그 정의와 두 갈래의 결과를 정리한다.

두 장벽을 함께 넘은 뒤

1990년 무렵 등장한 산술화(arithmetization)는 상대화 장벽을 넘어 IP = PSPACE 를 주었다. 한편 대각선 논법은 자연 증명 장벽에 걸리지 않는다. 둘을 결합하자 두 장벽을 동시에 피하는 회로 하한이 나왔다.

MA_EXP ⊄ P/poly (Buhrman·Fortnow·Thierauf, 1998)
모든 k 에 대해 PP ⊄ SIZE(n^k) (Vinodchandran, 2005)
모든 k 에 대해 PromiseMA ⊄ SIZE(n^k) (Santhanam, 2007)

여기서 MA 는 증명 검사에 무작위를 허용한 NP 이고, MA_EXP 는 그것의 지수 시간판이다. 그렇다면 같은 재료로 NEXP ⊄ P/poly, 나아가 P ≠ NP 까지 갈 수 있을까? Aaronson 과 Wigderson 은 2008년에 「갈 수 없다」는 정리를 내놓았다.

대수적 오라클과 대수화의 정의

산술화의 핵심은 불 논리식을 블랙박스로 다루지 않고 유한체 F 위의 저차 다항식으로 올려, 0 과 1 이 아닌 점에서도 계산하는 데 있다. 오라클에도 같은 능력을 주어 보자.

오라클 A 는 불 함수 Aₘ : {0,1}^m → {0,1} 의 모임이다. A 의 저차 확장(low-degree extension) Ã 는 각 Aₘ 을, 불 입력에서는 Aₘ 과 값이 같고 변수마다 차수가 상수로 묶인 다항식 Ãₘ : F^m → F 로 넓힌 것이다.

두 개의 점 격자로 그린 F 위의 m 차원 공간. 왼쪽의 보통 오라클 A 는 0 과 1 로만 된 불 입력 점에서만 값을 주고, 나머지 점은 비어 있다. 오른쪽의 저차 확장 A 물결은 격자의 모든 점에서 값을 주며, 불 입력 점에서는 A 와 값이 같다. — 오라클 A 와 그 저차 확장 Ã — Ã 는 불 입력 바깥의 점에서도 값을 준다(격자의 크기는 그림을 위한 예시).

대수화(algebrization)는 다음과 같이 정의한다.

포함 C ⊆ D 가 대수화한다: 모든 오라클 A 와 그 확장 Ã 에 대해 C^A ⊆ D^Ã 이다.
분리 C ⊄ D 가 대수화한다: 모든 A 와 Ã 에 대해 C^Ã ⊄ D^A 이다.

두 경우 모두 한쪽 클래스만 Ã 를 받는다. 저자들은 이 비대칭이 꼭 필요하다고 설명한다. 더 엄격하게 정의하면 기존의 대화형 증명 결과가 대수화함을 보일 수 없기 때문이다.

장벽으로 쓰는 논리는 상대화 때와 같다. 어떤 기법이 대수화한다면 그 기법으로 증명한 명제는 모든 A 와 Ã 에 대해 성립해야 한다. 따라서 반례가 되는 A 와 Ã 가 있는 명제는 그 기법만으로는 증명할 수 없다.

첫째 결과: 알려진 비상대화 결과는 대수화한다

모든 A 와 Ã 에 대해 다음이 성립한다.

증명된 정리

PSPACE^A ⊆ IP^Ã, NEXP^A ⊆ MIP^Ã

MA_EXP^Ã ⊄ P^A/poly, PromiseMA^Ã ⊄ SIZE^A(n^k)

Aaronson, Wigderson 2009

이유는 단순하다. 대화형 증명에서 검증자가 논리식을 산술화하다 오라클 게이트를 만나면, 불 값이 아닌 입력에서 그 게이트의 값이 필요해진다. 그때 Ã 에 물으면 된다. 회로 하한들은 대화형 증명 결과 하나에 상대화하는 논증을 이어 붙인 것이라 함께 대수화한다.

둘째 결과: 핵심 미해결 문제는 대수화하지 않는 기법을 요구한다

아래 각 줄을 만족하는 오라클 A 와 확장 Ã 가 존재한다.

존재하는 대수적 오라클 세계와, 그래서 대수화하는 기법으로는 증명할 수 없는 것
존재하는 오라클 세계	그래서 대수화하는 기법으로는 증명할 수 없는 것
NP^Ã ⊆ P^A	P ≠ NP
NP^A ⊄ P^Ã	P = NP
RP^A ⊄ P^Ã	P = RP (무작위의 제거)
NP^A ⊄ BPP^Ã	NP ⊆ BPP
NEXP^Ã ⊂ P^A/poly	NEXP ⊄ P/poly
NP^Ã ⊂ SIZE^A(n)	NP 에 대한 초선형 회로 하한

첫 줄은 쉽다. A 를 PSPACE-완전 언어로, Ã 를 PSPACE 안에서 계산되는 확장으로 잡으면 NP^Ã = P^A = PSPACE 다. 나머지는 어렵다. 불 함수의 저차 확장에까지 질의할 수 있는 알고리즘의 대수적 질의 복잡도라는 새 모형에서 하한을 증명해야 한다. 저자들은 적대적 다항식을 직접 구성하는 방법과, 통신 복잡도의 하한을 옮겨 오는 방법 두 가지를 썼다.

무엇을 설명하는가

저자들의 요약은 「대수화는 지난 20년의 비상대화 기법이 닿는 한계를 거의 정확히 그어 준다」는 것이다. MA_EXP 에 대한 초다항 회로 하한은 증명되는데 NEXP 에 대해서는 안 되는 까닭, PromiseMA 에 대한 초선형 하한은 되는데 NP 에 대해서는 안 되는 까닭이 여기에 있다.

그 뒤의 전개

정의 다듬기. Aaronson 의 2017년 개관에 따르면 Impagliazzo·Kabanets·Kolokolova 는 모든 클래스가 같은 대수적 오라클을 받는 공리적 정의를 주었지만 NEXP ⊄ P/poly 에 관한 결론은 잃었고, Aydınlıoğlu 와 Bach 가 「아핀 상대화」로 둘을 함께 얻었다.
다루지 않은 결과. 원 논문은 작은 깊이 회로 하한, SAT 의 시간–공간 하한 같은 일부 비상대화 결과를 이 틀로 다루지 않았다고 밝힌다.
넘은 예. 2011년 Williams 의 NEXP ⊄ ACC⁰ 는 상대화도 대수화도 하지 않는 하한으로 평가된다. 반례가 되는 오라클을 실제로 만들 수 있기 때문이다.

출처

S. Aaronson, A. Wigderson, "Algebrization: A New Barrier in Complexity Theory", ACM Trans. Comput. Theory 1(1), 1–54 (2009); STOC 2008. 저자 공개본에서 초록, §1(결과 목록과 기법), 정의 2.1–2.3 과 그 해설, 각주 1 을 확인. 서지는 DOI 등록 정보로 확인.
H. Buhrman, L. Fortnow, T. Thierauf, "Nonrelativizing Separations", CCC 1998, 8–12. 서지는 DOI 등록 정보로, 내용은 Aaronson·Wigderson 2009 §1.1 과 Aaronson 2017 정리 56 으로 확인.
N. V. Vinodchandran, "A Note on the Circuit Complexity of PP", Theoret. Comput. Sci. 347, 415–418 (2005). 서지는 DOI 등록 정보로, 내용은 위 두 문헌으로 확인.
R. Santhanam, "Circuit Lower Bounds for Merlin–Arthur Classes", STOC 2007, 275–283. 서지는 DOI 등록 정보로, 내용은 위 두 문헌으로 확인.
R. Impagliazzo, V. Kabanets, A. Kolokolova, "An Axiomatic Approach to Algebrization", STOC 2009, 695–704. 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §6.3.3 으로 확인.
B. Aydınlıoğlu, E. Bach, "Affine Relativization: Unifying the Algebrization and Relativization Barriers", ACM Trans. Comput. Theory 10(1) (2018). 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §6.3.3 으로 확인.
R. Williams, "Nonuniform ACC Circuit Lower Bounds", J. ACM 61(1), 1–32 (2014). 저자 공개본의 초록을 확인.
S. Aaronson, "P =? NP", 저자 공개본(2017). §6.3.2–§6.3.3, §6.4.2 를 확인.

출처·이용 조건: 직접 작성

참고문헌 8

장벽원문 확인
Algebrization: A New Barrier in Complexity TheoryScott Aaronson, Avi Wigderson · 2009ACM Transactions on Computation Theory 1(1), 1–54쪽 (2009) · 학회 발표 STOC 2008 (Proceedings of the 40th Annual ACM Symposium on Theory of Computing), 731–740쪽
상대화를 넘어선 산술화 기법에도 한계가 있음을 보인, 대수화 장벽의 원전이다. 초록과 서론이 상대화·자연 증명·대수화 세 장벽의 관계를 정리하고 있어 2-2 를 깊이 읽으려는 독자의 다음 단계로 알맞다. 본론은 전문 연구자용이다. Aaronson 의 누리집에 있는 공개본으로 연결한다.
확인:저자 공개본을 열어 초록, §1, 정의 2.1–2.3 을 읽음.
원문 주소 (www.scottaaronson.com)
부분 결과서지만 확인
Nonrelativizing SeparationsH. Buhrman, L. Fortnow, T. Thierauf · 1998Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 8–12쪽 (1998)
MA_EXP 에는 다항 크기 회로가 없음(MA_EXP ⊄ P/poly)을 보인 논문이다. 산술화와 대각선 논법을 결합해 상대화와 자연 증명 두 장벽을 함께 피한 회로 하한의 예로, 2-2 의 대수화 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson–Wigderson 2009 §1.1 과 Aaronson 2017 정리 56 으로 확인.
원문 주소 (doi.org)DOI 10.1109/ccc.1998.694585
부분 결과서지만 확인
A Note on the Circuit Complexity of PPN. V. Vinodchandran · 2005Theoretical Computer Science 347(1–2), 415–418쪽 (2005)
모든 k 에 대해 PP 가 크기 n^k 의 회로를 갖지 않음을 보인 논문이다. 산술화와 대각선 논법을 결합해 두 장벽을 함께 피한 회로 하한의 예로, 2-2 의 대수화 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson–Wigderson 2009 §1.1 과 Aaronson 2017 로 확인.
원문 주소 (doi.org)DOI 10.1016/j.tcs.2005.07.032
부분 결과서지만 확인
Circuit Lower Bounds for Merlin–Arthur ClassesR. Santhanam · 2007STOC 2007 (Proceedings of the 39th Annual ACM Symposium on Theory of Computing), 275–283쪽
모든 k 에 대해 PromiseMA 가 크기 n^k 의 회로를 갖지 않음을 보인 논문이다. 산술화와 대각선 논법을 결합해 두 장벽을 함께 피한 회로 하한의 예로, 2-2 의 대수화 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson–Wigderson 2009 §1.1 과 Aaronson 2017 로 확인.
원문 주소 (doi.org)DOI 10.1145/1250790.1250832
장벽서지만 확인
An Axiomatic Approach to AlgebrizationR. Impagliazzo, V. Kabanets, A. Kolokolova · 2009STOC 2009 (Proceedings of the 41st Annual ACM Symposium on Theory of Computing), 695–704쪽
대수화를, 모든 클래스가 같은 대수적 오라클을 받는 공리적 정의로 다시 세운 논문이다. Aaronson 의 2017년 개관에 따르면 이 정의에서는 NEXP ⊄ P/poly 에 관한 결론을 잃는다. 2-2 의 대수화 글이 「그 뒤의 전개」에서 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.3 으로 확인.
원문 주소 (doi.org)DOI 10.1145/1536414.1536509
장벽서지만 확인
Affine Relativization: Unifying the Algebrization and Relativization BarriersB. Aydınlıoğlu, E. Bach · 2018ACM Transactions on Computation Theory 10(1), 1–67쪽 (2018) · 예비 공개 ECCC TR16-040 (2016)
상대화와 대수화 두 장벽을 「아핀 상대화」라는 하나의 틀로 묶은 논문이다. Aaronson 의 2017년 개관에 따르면, 대수화의 공리적 정의와 NEXP ⊄ P/poly 에 관한 결론을 함께 얻는다. 2-2 의 대수화 글이 「그 뒤의 전개」에서 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.3 으로 확인.
원문 주소 (doi.org)DOI 10.1145/3170704
부분 결과원문 확인
Nonuniform ACC Circuit Lower BoundsRyan Williams · 2014Journal of the ACM 61(1), 1–32쪽 (2014) · 학회 발표 CCC 2011 (26th Annual IEEE Conference on Computational Complexity), 115–125쪽
NEXP 의 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. 회로의 충족 가능성을 전수 조사보다 조금이라도 빨리 푸는 알고리즘을 만들면 회로 하한이 따라 나온다는 연결을 써서, 알고리즘 설계로 하한을 증명했다. 알려진 장벽들을 피한 드문 사례로 꼽힌다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본(2012-07-31 판)을 열어 초록, 서론, 정리 1.1·1.2 를 읽음.
원문 주소 (people.csail.mit.edu)
개관원문 확인
P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음.
원문 주소 (www.scottaaronson.com)

하위 정보 0

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

아직 없습니다.