단조 회로 하한 — NOT 없이는 클릭 문제를 풀 수 없다

Razborov 는 1985년에 AND 와 OR 만 쓰는 단조 회로로 클릭 문제를 풀려면 다항식보다 빨리 커지는 크기가 든다는 것을 증명했다. NP-완전 문제를 상대로 다항식을 넘는 하한을 얻은 결과였지만, NOT 게이트 하나가 이 방법과 일반 회로 사이를 가로막는다.

중급
관리자
2026-10-05 23:05
조회 0
AI 도움

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

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

Razborov 는 1985년에 AND 와 OR 만 쓰는 단조 회로로 클릭 문제를 풀려면 다항식보다 빨리 커지는 크기가 든다는 것을 증명했다. 이 글은 그 진술과 근사 방법의 얼개를 보고, NOT 게이트 하나가 왜 이 방법과 일반 회로 사이를 가로막는지 짚는다.

핵심 정리

단조 회로는 AND 와 OR 만 쓰고 NOT 은 쓰지 않는다. 클릭 문제는 단조 함수이고 NP-완전이다.
Razborov(1985): 클릭 크기 s 를 ln m 의 4분의 1 쯤으로 잡으면, 그것을 계산하는 단조 회로의 게이트 수는 m^(C·log m) 이상이다. 어떤 다항식보다도 빨리 커지는 값이다.
증명은 근사 방법이다. 게이트마다 함수를 단순한 꼴로 바꿔치기하고, 그때 쌓이는 오류를 센다.
같은 논문의 정리 3 에 따르면 P 에 속하는 매칭 문제도 단조 회로로는 m^(C·log m) 이상이 든다. 단조 하한이 말해 주는 것은 문제의 어려움이 아니라 단조 회로의 약함일 수 있다.
클릭 문제가 NOT 을 쓰는 일반 회로로도 다항 크기에 풀리지 않는다는 명제는 지금도 증명되지 않았다.

정확한 진술

단조 회로(monotone circuit)는 AND 와 OR 게이트만 쓰고 NOT 게이트는 쓰지 않는 논리 회로다. 이런 회로가 계산하는 함수는 단조 함수다. 입력 비트 하나를 0 에서 1 로 바꾸었을 때 출력이 1 에서 0 으로 떨어지는 일이 없다는 뜻이다.

클릭 문제는 그래프에 서로 모두 이어진 꼭짓점 k 개(클릭)가 있는지 묻는다. 꼭짓점이 m 개인 그래프는 변이 있고 없음을 나타내는 비트 m(m−1)/2 개로 적는다. 변을 더한다고 있던 클릭이 사라지지는 않으므로 이 함수는 단조다. 그리고 클릭 문제는 NP-완전이다.

단조 회로의 보기. 꼭짓점 1, 2, 3, 4 로 된 그래프의 여섯 변(1–2, 1–3, 1–4, 2–3, 2–4, 3–4)이 있는지를 나타내는 비트가 맨 아래 입력이다. 그 위의 AND 게이트 넷은 각각 삼각형 1·2·3, 1·2·4, 1·3·4, 2·3·4 를 이루는 세 변을 받고, 맨 위의 OR 게이트가 넷을 모은다. 오른쪽에는 줄이 그어진 NOT 게이트와 함께 NOT 은 쓰지 않는다는 설명, 변을 더해도 출력이 1 에서 0 으로 떨어지지 않는다는 설명이 있다. — 보기: 꼭짓점 4 개 그래프에 크기 3 의 클릭(삼각형)이 있는지 계산하는 단조 회로. AND 와 OR 만 쓴다.

Razborov 가 1985년에 증명한 정리는 다음과 같다. 꼭짓점 m 개인 그래프에 크기 s 이상의 클릭이 있는지 계산하는 단조 회로의 게이트 수를 L 이라 하자.

Razborov 의 단조 회로 하한 증명됨

s 가 상수이면 L 은 m^s/(log m)^(2s) 의 상수 배 이상이다. s 를 ln m 의 4분의 1 쯤으로 잡으면 L 은 m^(C·log m) 이상이다(C 는 양의 상수).

둘째 줄이 핵심이다. m^(C·log m) 은 어떤 다항식보다도 빨리 커진다. 2년 뒤 Alon 과 Boppana 가 이를 지수 크기로 끌어올렸다. 교과서에 실리는 꼴은 「어떤 상수 ε > 0 이 있어, k ≤ n^(1/4) 이면 꼭짓점 n 개 그래프의 k-클릭을 판정하는 단조 회로는 크기가 2^(ε√k) 이상」이다.

뜻

Razborov 의 논문에 따르면, 그때까지 NP 에 속하는 단조 함수에 대해 알려진 가장 좋은 단조 회로 하한은 변수 수 n 에 대해 n²/log n 수준이었다. 그것이 단번에 다항식을 넘어섰다. Aaronson 은 당시 대학원생이던 Razborov 가 이 결과로 복잡도 이론 학계를 놀라게 했다고 적는다. 단, 「NOT 을 쓰지 않는다면」이라는 조건이 붙어 있다.

증명의 핵심 생각 — 근사 방법

Razborov 의 방법은 근사 방법(method of approximations)이라 불린다. 교과서의 서술을 따라 얼개만 적는다.

회로의 게이트마다 그 게이트가 계산하는 함수를 「단순한 꼴」의 함수로 바꿔치기한다. 단순한 꼴이란 「꼭짓점 집합 S 가 통째로 클릭인가」를 묻는 함수 몇 개의 OR 이다. S 는 작은 집합이어야 하고 개수에도 상한을 둔다.
시험 입력을 두 무리 준비한다. 「예」 쪽은 k-클릭 하나만 있고 다른 변은 없는 그래프다. 「아니오」 쪽은 꼭짓점을 k−1 가지 색으로 무작위로 칠하고 색이 다른 꼭짓점끼리만 이은 그래프다. 뒤쪽에는 k-클릭이 있을 수 없다.
게이트 하나를 바꿔치기할 때 새로 틀리게 되는 시험 입력은 아주 적다. 여기서 개수 상한을 지키려고 함수들을 합치는 데 Erdős–Rado 의 해바라기 보조정리가 쓰인다.
그런데 단순한 꼴의 함수는 어느 것이든 「예」 무리의 대부분에서 틀리거나 「아니오」 무리의 대부분에서 틀린다. 클릭 문제를 제대로 구별하지 못한다.
따라서 원래 회로가 옳다면, 조금씩 쌓인 오류가 큰 오류가 될 만큼 게이트가 많았어야 한다.

두 가지 시험 입력을 k 가 4 인 경우로 그린 그림. 왼쪽 「예」 쪽 그래프는 꼭짓점 여섯 개 가운데 네 개가 서로 모두 이어진 4-클릭 하나만 있고 나머지 두 꼭짓점에는 변이 없다. 오른쪽 「아니오」 쪽 그래프는 꼭짓점 여섯 개를 세 가지 색으로 두 개씩 칠하고 색이 다른 꼭짓점끼리만 이었다. 같은 색끼리는 이어지지 않으므로 4-클릭이 있을 수 없다. — k = 4 일 때의 두 시험 입력 보기. 「아니오」 쪽은 같은 색 꼭짓점끼리 이어지지 않으므로, 꼭짓점 넷을 고르면 그 가운데 둘은 색이 같아 이어지지 않는다.

왜 일반 회로로 넘어가지 못하나

기대는 이랬다. 단조 함수를 계산하는 일반 회로를 크기를 크게 늘리지 않고 단조 회로로 고칠 수 있다면, 위 정리에서 곧바로 「클릭 문제에는 다항 크기 회로가 없다」가 나온다. 그것은 P ≠ NP 보다도 센 결론이다.

이 기대를 무너뜨린 것은 Razborov 자신의 같은 논문이었다. 정리 3 은 이분 그래프에 완전 매칭이 있는지 묻는 함수(논리적 퍼머넌트)의 단조 회로 크기도 m^(C·log m) 이상임을 말한다. 그런데 매칭 문제는 P 에 속하고, NOT 을 쓰는 일반 회로로는 다항 크기에 계산된다. 단조 회로와 일반 회로의 간격이 다항식을 넘을 수 있다는 것이다. Tardos 는 1988년에 이 간격이 지수적일 수 있음을 보였다.

단조 회로 (NOT 없음)

완전 매칭 함수에도 m^(C·log m) 이상의 크기가 든다.

일반 회로 (NOT 허용)

매칭 문제는 P 에 속하고, 다항 크기에 계산된다.

P 대 NP 까지의 거리

거리는 NOT 게이트 하나만큼인데, 그 하나가 멀다. 클릭 문제가 NOT 을 쓰는 일반 회로로도 다항 크기에 풀리지 않는다는 명제는 지금도 증명되지 않았다. Fortnow 는 2009년 글에서 Razborov 의 결과를 일반 회로로 넓히면 P ≠ NP 가 증명된다고 적고, 곧이어 그 기법이 NOT 게이트 앞에서 무너진다는 것도 Razborov 가 보였다고 덧붙인다.

남은 교훈은 둘이다. 조합론의 도구로 NP-완전 문제에 대한 진짜 하한을 얻을 수 있다는 것, 그리고 제한된 모형에서 얻은 하한을 일반 모형으로 옮기는 일은 별개의 문제라는 것이다.

출처

A. A. Razborov, "Lower bounds on the monotone complexity of some Boolean functions", Doklady Akademii Nauk SSSR 281(4), 1985, 798–801. 서지: https://www.mathnet.ru/eng/dan9192 · 영어판(Soviet Mathematics Doklady 31, 354–357): https://people.cs.uchicago.edu/~razborov/files/clique.pdf (정리 2 의 두 하한, 정리 3 과 그 뒤의 설명)
Scott Aaronson, "P =? NP", 2017. https://www.scottaaronson.com/papers/pnp.pdf (6.2.2절: 정리 47·48, Alon–Boppana 의 개선, 해바라기 보조정리, 단조 회로의 약함에 대한 평가)
Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. 저자 공개 초고: https://theory.cs.princeton.edu/complexity/ (정리 13.9 와 13.3.1절의 증명, 장 끝의 역사 주석)
Lance Fortnow, "The status of the P versus NP problem", Communications of the ACM 52(9), 2009, 78–86. https://lance.fortnow.com/papers/files/pnp-cacm.pdf (4.2절 회로 복잡도)
N. Alon, R. B. Boppana, "The monotone circuit complexity of Boolean functions", Combinatorica 7(1), 1987, 1–22. https://doi.org/10.1007/BF02579196 (서지만 확인)
É. Tardos, "The gap between monotone and non-monotone circuit complexity is exponential", Combinatorica 8(1), 1988, 141–142. https://doi.org/10.1007/BF02122563 (서지만 확인)
A. A. Razborov, "On the method of approximations", STOC 1989, 167–176. https://doi.org/10.1145/73007.73023 (서지만 확인)

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

참고문헌 7

부분 결과원문 확인
Lower bounds on the monotone complexity of some Boolean functionsAlexander A. Razborov · 1985Doklady Akademii Nauk SSSR 281(4), 798–801쪽 (1985, 러시아어) · 영문 번역 Soviet Mathematics Doklady 31, 354–357쪽 (1985)
NOT 을 쓰지 않는 단조 회로로는 클릭 문제를 다항 크기에 풀 수 없음을 증명한 논문이다. NP-완전 문제에 대한 초다항 회로 하한을 (단조 회로라는 제한 아래) 처음 얻어 큰 기대를 모았다. 다만 이 방법은 일반 회로로 넓혀지지 않았다. 연결한 것은 저자가 올린 영문 번역본이며, 러시아어 원문의 서지는 Math-Net.Ru(mathnet.ru/eng/dan9192)에 있다.
확인:저자 누리집의 영문 번역본을 열어 정리 2·정리 3 과 그 설명을 읽음. 러시아어 원문의 서지는 Math-Net.Ru 로 확인.
원문 주소 (people.cs.uchicago.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)
교과서원문 확인
Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009
계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.
확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
원문 주소 (theory.cs.princeton.edu)
개관원문 확인
The status of the P versus NP problemLance Fortnow · 2009Communications of the ACM 52(9), 78–86쪽 (2009)
P 대 NP 문제의 의미와 2009년 시점의 연구 상황을 전산학 일반 독자에게 풀어 쓴 개관이다. 문제를 풀려던 시도들과 그 한계, NP-완전 문제를 현실에서 다루는 법, 양자 컴퓨터의 가능성까지 짧게 훑는다. 수식이 거의 없어 입문 독자가 처음 읽을 영어 글로 알맞다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본을 열어 인용한 절들을 읽음.
원문 주소 (lance.fortnow.com)
부분 결과서지만 확인
The Monotone Circuit Complexity of Boolean FunctionsN. Alon, R. B. Boppana · 1987Combinatorica 7(1), 1–22쪽 (1987)
Razborov 의 단조 회로 하한을 지수 크기로 끌어올린 논문이다. 클릭 문제를 푸는 단조 회로의 크기 하한을 다항식을 넘는 수준에서 지수 수준으로 강화했다. 2-3 의 회로 하한 글과 2-4 의 단조 회로 하한 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.2.2 와 Arora–Barak 공개 초고 13장으로 확인.
원문 주소 (doi.org)DOI 10.1007/bf02579196
부분 결과서지만 확인
The Gap between Monotone and Non-Monotone Circuit Complexity Is ExponentialÉ. Tardos · 1988Combinatorica 8(1), 141–142쪽 (1988)
단조 회로와 일반 회로의 크기 차이가 지수적일 수 있음을 보인 두 쪽짜리 논문이다. 단조 회로 하한이 문제의 어려움이 아니라 단조 회로의 약함을 말해 줄 수 있음을 보여 준다. 2-3 의 회로 하한 글과 2-4 의 단조 회로 하한 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.2.2 와 Arora–Barak 공개 초고 13장으로 확인.
원문 주소 (doi.org)DOI 10.1007/bf02122563
부분 결과서지만 확인
On the method of approximationsA. A. Razborov · 1989STOC 1989 (Proceedings of the 21st Annual ACM Symposium on Theory of Computing), 167–176쪽
근사 방법이 NOT 게이트를 허용한 일반 회로에는 통하기 어렵다는 것을 보인 논문이다. 단조 회로 하한의 방법을 일반 회로로 넓히기 어려운 까닭을, 그 방법을 만든 저자 자신이 밝혔다. 2-4 의 단조 회로 하한 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Fortnow 2009 §4.2 등으로 확인.
원문 주소 (doi.org)DOI 10.1145/73007.73023

하위 정보 0

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

아직 없습니다.